結果
問題 | No.2604 Initial Motion |
ユーザー |
|
提出日時 | 2024-01-12 22:00:38 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 519 ms / 3,000 ms |
コード長 | 3,841 bytes |
コンパイル時間 | 2,219 ms |
コンパイル使用メモリ | 216,564 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-27 22:11:46 |
合計ジャッジ時間 | 12,187 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 13 ms
6,944 KB |
testcase_04 | AC | 15 ms
6,944 KB |
testcase_05 | AC | 14 ms
6,940 KB |
testcase_06 | AC | 14 ms
6,940 KB |
testcase_07 | AC | 14 ms
6,940 KB |
testcase_08 | AC | 14 ms
6,940 KB |
testcase_09 | AC | 14 ms
6,940 KB |
testcase_10 | AC | 14 ms
6,944 KB |
testcase_11 | AC | 15 ms
6,940 KB |
testcase_12 | AC | 14 ms
6,940 KB |
testcase_13 | AC | 465 ms
6,940 KB |
testcase_14 | AC | 355 ms
6,940 KB |
testcase_15 | AC | 188 ms
6,940 KB |
testcase_16 | AC | 444 ms
6,940 KB |
testcase_17 | AC | 519 ms
6,940 KB |
testcase_18 | AC | 519 ms
6,944 KB |
testcase_19 | AC | 510 ms
6,940 KB |
testcase_20 | AC | 419 ms
6,940 KB |
testcase_21 | AC | 358 ms
6,944 KB |
testcase_22 | AC | 490 ms
6,944 KB |
testcase_23 | AC | 365 ms
6,944 KB |
testcase_24 | AC | 458 ms
6,940 KB |
testcase_25 | AC | 396 ms
6,940 KB |
testcase_26 | AC | 396 ms
6,944 KB |
testcase_27 | AC | 295 ms
6,944 KB |
testcase_28 | AC | 371 ms
6,940 KB |
testcase_29 | AC | 475 ms
6,948 KB |
testcase_30 | AC | 332 ms
6,940 KB |
testcase_31 | AC | 393 ms
6,940 KB |
testcase_32 | AC | 316 ms
6,940 KB |
testcase_33 | AC | 105 ms
6,944 KB |
testcase_34 | AC | 89 ms
6,940 KB |
testcase_35 | AC | 97 ms
6,944 KB |
testcase_36 | AC | 78 ms
6,940 KB |
testcase_37 | AC | 30 ms
6,944 KB |
testcase_38 | AC | 3 ms
6,940 KB |
testcase_39 | AC | 3 ms
6,944 KB |
testcase_40 | AC | 88 ms
6,940 KB |
testcase_41 | AC | 90 ms
6,948 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'; }