結果
| 問題 | No.2604 Initial Motion |
| ユーザー |
👑  hos.lyric
|
| 提出日時 | 2024-01-12 21:39:06 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 459 ms / 3,000 ms |
| コード長 | 5,975 bytes |
| コンパイル時間 | 1,531 ms |
| コンパイル使用メモリ | 129,016 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-09-27 21:36:06 |
| 合計ジャッジ時間 | 11,517 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 39 |
ソースコード
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
// Minimum cost flow by successive shortest paths.
// Assumes that there exists no negative-cost cycle.
// TODO: Check the range of intermediate values.
template <class Flow, class Cost> struct MinCostFlow {
// Watch out when using types other than int and long long.
static constexpr Flow FLOW_EPS = 1e-10L;
static constexpr Flow FLOW_INF = std::numeric_limits<Flow>::max();
static constexpr Cost COST_EPS = 1e-10L;
static constexpr Cost COST_INF = std::numeric_limits<Cost>::max();
int n, m;
vector<int> ptr, nxt, zu;
vector<Flow> capa;
vector<Cost> cost;
explicit MinCostFlow(int n_) : n(n_), m(0), ptr(n_, -1) {}
void ae(int u, int v, Flow w, Cost c) {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
assert(0 <= w);
nxt.push_back(ptr[u]); zu.push_back(v); capa.push_back(w); cost.push_back( c); ptr[u] = m++;
nxt.push_back(ptr[v]); zu.push_back(u); capa.push_back(0); cost.push_back(-c); ptr[v] = m++;
}
vector<Cost> pot, dist;
vector<bool> vis;
vector<int> pari;
// cost slopes[j] per flow when flows[j] <= flow <= flows[j + 1]
vector<Flow> flows;
vector<Cost> slopes;
// Finds a shortest path from s to t in the residual graph.
// O((n + m) log m) time.
// Assumes that the members above are set.
// The distance to a vertex might not be determined if it is >= dist[t].
// You can pass t = -1 to find a shortest path to each vertex.
void shortest(int s, int t) {
using Entry = pair<Cost, int>;
priority_queue<Entry, vector<Entry>, std::greater<Entry>> que;
for (int u = 0; u < n; ++u) { dist[u] = COST_INF; vis[u] = false; }
for (que.emplace(dist[s] = 0, s); !que.empty(); ) {
const Cost c = que.top().first;
const int u = que.top().second;
que.pop();
if (vis[u]) continue;
vis[u] = true;
if (u == t) return;
for (int i = ptr[u]; ~i; i = nxt[i]) if (capa[i] > FLOW_EPS) {
const int v = zu[i];
if (!vis[v]) {
const Cost cc = c + cost[i] + pot[u] - pot[v];
if (dist[v] > cc) { que.emplace(dist[v] = cc, v); pari[v] = i; }
}
}
}
}
// Finds a minimum cost flow from s to t of amount min{(max flow), limFlow}.
// Bellman-Ford takes O(n m) time, or O(m) time if there is no negative-cost
// edge, or cannot stop if there exists a negative-cost cycle.
// min{(max flow), limFlow} shortest paths if Flow is an integral type.
pair<Flow, Cost> run(int s, int t, Flow limFlow = FLOW_INF) {
assert(0 <= s); assert(s < n);
assert(0 <= t); assert(t < n);
assert(s != t);
assert(0 <= limFlow);
pot.assign(n, 0);
for (; ; ) {
bool upd = false;
for (int i = 0; i < m; ++i) if (capa[i] > FLOW_EPS) {
const int u = zu[i ^ 1], v = zu[i];
const Cost cc = pot[u] + cost[i];
if (pot[v] > cc + COST_EPS) { pot[v] = cc; upd = true; }
}
if (!upd) break;
}
dist.resize(n);
vis.resize(n);
pari.resize(n);
Flow totalFlow = 0;
Cost totalCost = 0;
flows.clear(); flows.push_back(0);
slopes.clear();
for (; totalFlow < limFlow; ) {
shortest(s, t);
if (!vis[t]) break;
for (int u = 0; u < n; ++u) pot[u] += min(dist[u], dist[t]);
Flow f = limFlow - totalFlow;
for (int v = t; v != s; ) {
const int i = pari[v]; if (f > capa[i]) { f = capa[i]; } v = zu[i ^ 1];
}
for (int v = t; v != s; ) {
const int i = pari[v]; capa[i] -= f; capa[i ^ 1] += f; v = zu[i ^ 1];
}
totalFlow += f;
totalCost += f * (pot[t] - pot[s]);
flows.push_back(totalFlow);
slopes.push_back(pot[t] - pot[s]);
}
return make_pair(totalFlow, totalCost);
}
};
////////////////////////////////////////////////////////////////////////////////
int K, N, M;
vector<int> A;
vector<int> B;
vector<int> U, V;
vector<Int> D;
int main() {
for (; ~scanf("%d%d%d", &K, &N, &M); ) {
A.resize(K);
for (int k = 0; k < K; ++k) {
scanf("%d", &A[k]);
--A[k];
}
B.resize(N);
for (int u = 0; u < N; ++u) {
scanf("%d", &B[u]);
}
U.resize(M);
V.resize(M);
D.resize(M);
for (int i = 0; i < M; ++i) {
scanf("%d%d%lld", &U[i], &V[i], &D[i]);
--U[i];
--V[i];
}
MinCostFlow<int, Int> mcf(N + 2);
const int src = N, snk = N + 1;
for (int k = 0; k < K; ++k) {
mcf.ae(src, A[k], 1, 0);
}
for (int u = 0; u < N; ++u) {
mcf.ae(u, snk, B[u], 0);
}
for (int i = 0; i < M; ++i) {
mcf.ae(U[i], V[i], K, D[i]);
mcf.ae(V[i], U[i], K, D[i]);
}
const auto res = mcf.run(src, snk, K);
assert(res.first == K);
printf("%lld\n", res.second);
}
return 0;
}