結果
問題 |
No.3201 Corporate Synergy
|
ユーザー |
|
提出日時 | 2025-07-11 22:20:54 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 713 bytes |
コンパイル時間 | 3,546 ms |
コンパイル使用メモリ | 287,660 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-07-11 22:20:59 |
合計ジャッジ時間 | 4,456 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; #include <atcoder/maxflow> using atcoder::mf_graph; int main(){ int n; cin>>n; vector<ll> p(n); for(int i=0;i<n;i++)cin>>p[i]; mf_graph<ll> graph(n+202); ll ans=0; for(int i=0;i<n;i++){ if(p[i]>=0){ ans+=p[i]; graph.add_edge(n,i,p[i]); }else{ graph.add_edge(i,n+1,-p[i]); } } ll inf=1e18; int m; cin>>m; for(int i=0;i<m;i++){ int u,v; cin>>u>>v; u--;v--; graph.add_edge(v,u,inf); } int k; cin>>k; for(int i=0;i<k;i++){ int a,b; ll s; cin>>a>>b>>s; a--;b--; ans+=s; graph.add_edge(n,n+2+i,s); graph.add_edge(n+2+i,a,inf); graph.add_edge(n+2+i,b,inf); } cout<<ans-graph.flow(n,n+1)<<endl; }