結果
問題 | No.2604 Initial Motion |
ユーザー | Jeroen Op de Beek |
提出日時 | 2024-01-12 22:00:38 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 593 ms / 3,000 ms |
コード長 | 3,841 bytes |
コンパイル時間 | 2,605 ms |
コンパイル使用メモリ | 217,688 KB |
実行使用メモリ | 6,548 KB |
最終ジャッジ日時 | 2024-01-12 22:00:59 |
合計ジャッジ時間 | 13,730 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,548 KB |
testcase_01 | AC | 2 ms
6,548 KB |
testcase_02 | AC | 2 ms
6,548 KB |
testcase_03 | AC | 15 ms
6,548 KB |
testcase_04 | AC | 16 ms
6,548 KB |
testcase_05 | AC | 16 ms
6,548 KB |
testcase_06 | AC | 15 ms
6,548 KB |
testcase_07 | AC | 15 ms
6,548 KB |
testcase_08 | AC | 15 ms
6,548 KB |
testcase_09 | AC | 15 ms
6,548 KB |
testcase_10 | AC | 15 ms
6,548 KB |
testcase_11 | AC | 21 ms
6,548 KB |
testcase_12 | AC | 16 ms
6,548 KB |
testcase_13 | AC | 521 ms
6,548 KB |
testcase_14 | AC | 388 ms
6,548 KB |
testcase_15 | AC | 228 ms
6,548 KB |
testcase_16 | AC | 486 ms
6,548 KB |
testcase_17 | AC | 562 ms
6,548 KB |
testcase_18 | AC | 593 ms
6,548 KB |
testcase_19 | AC | 553 ms
6,548 KB |
testcase_20 | AC | 484 ms
6,548 KB |
testcase_21 | AC | 395 ms
6,548 KB |
testcase_22 | AC | 580 ms
6,548 KB |
testcase_23 | AC | 408 ms
6,548 KB |
testcase_24 | AC | 499 ms
6,548 KB |
testcase_25 | AC | 436 ms
6,548 KB |
testcase_26 | AC | 445 ms
6,548 KB |
testcase_27 | AC | 357 ms
6,548 KB |
testcase_28 | AC | 417 ms
6,548 KB |
testcase_29 | AC | 496 ms
6,548 KB |
testcase_30 | AC | 380 ms
6,548 KB |
testcase_31 | AC | 428 ms
6,548 KB |
testcase_32 | AC | 349 ms
6,548 KB |
testcase_33 | AC | 140 ms
6,548 KB |
testcase_34 | AC | 96 ms
6,548 KB |
testcase_35 | AC | 107 ms
6,548 KB |
testcase_36 | AC | 87 ms
6,548 KB |
testcase_37 | AC | 35 ms
6,548 KB |
testcase_38 | AC | 3 ms
6,548 KB |
testcase_39 | AC | 2 ms
6,548 KB |
testcase_40 | AC | 98 ms
6,548 KB |
testcase_41 | AC | 101 ms
6,548 KB |
ソースコード
#include "bits/stdc++.h" using namespace std; #define all(x) begin(x),end(x) template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; } #define debug(a) cerr << "(" << #a << ": " << a << ")\n"; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pi; const int mxN = 1e4+1; const ll oo = 3e18; struct mincostflow { // Source is Node 0; // Sink is node n-1 struct edge { ll f,c; int to; ll cost; }; typedef vector<edge> ve; vector<vector<int>> adj; vector<edge> edges; int n; mincostflow(int _n) { n=_n; adj.resize(n); dist.resize(n); parent.resize(n); pflow.resize(n); } void addEdge(int a, int b, ll w, ll cost, bool directed = true) { adj[a].push_back((int)edges.size()); adj[b].push_back((int)edges.size()+1); edges.push_back({0,w,b,cost}); edges.push_back({0,directed?0:w,a,-cost}); } bitset<mxN> inqueue; vector<ll> dist, pflow; vi parent; void SPFA() { fill(all(dist),oo); queue<int> q; q.push(0); parent[0] = -1; dist[0] = 0; inqueue[0]= true; pflow[0] = oo; while(!q.empty()) { int at = q.front(); q.pop(); inqueue[at] = false; for(int ei: adj[at]) { auto& e = edges[ei]; if(e.c-e.f<1) continue; ll constraint = min(e.c-e.f,pflow[at]); if(dist[at]+e.cost < dist[e.to]) { parent[e.to] = ei; pflow[e.to] = constraint; dist[e.to] = dist[at]+e.cost; if(!inqueue[e.to]) { inqueue[e.to] = true; q.push(e.to); } } else if(dist[at]+e.cost==dist[e.to]) { if(pflow[e.to]< constraint) { parent[e.to] = ei; pflow[e.to] = constraint; } } } } } void findPath(ll extra) { int at = n-1; while(at!=0) { int ei = parent[at]; auto& e = edges[ei]; e.f+=extra; auto& o = edges[ei^1]; o.f-=extra; at = o.to; } } pair<ll,ll> solve(int k) { ll flow = 0, cost = 0; while(true) { SPFA(); if(dist[n-1]==oo) { break; } int extraflow = pflow[n-1]; ll shortestpath = dist[n-1]; // debug(shortestpath); // debug(extraflow); if(flow+extraflow>=k) { cost+=shortestpath*(k-flow); flow = k; break; } flow+=extraflow; cost+=shortestpath*extraflow; findPath(pflow[n-1]); } return {flow,cost}; } }; int main() { int k,n,m; cin >> k >> n >> m; mincostflow mcf(n+2); for(int i=0;i<k;++i) { int a; cin >> a; mcf.addEdge(0,a,1,0); } for(int i=1;i<=n;++i) { int b; cin >> b; if(b) { mcf.addEdge(i,n+1,b,0); } } for(int i=0;i<m;++i) { ll w; int u,v; cin >> u >> v >> w; mcf.addEdge(u,v,1e9,w); mcf.addEdge(v,u,1e9,w); } auto [flow,res] = mcf.solve(1e9); cout << res << '\n'; }