fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl '\n'
  4. #ifndef ONLINE_JUDGE
  5. #define show(a) cout<<""#a""<<" is "<<a<<endl;
  6. #define shw(a,b)cout<<"-->"<<a<<" "<<b<<endl;
  7. #define print(arr,xx)for(int i=0;i<xx;i++)cout<<arr[i]<<" \n"[i==xx-1];
  8. #define here cout<<"here\n";
  9. #define fastio ;
  10. #else
  11. #define show(a)  ;
  12. #define shw(a,b) ;
  13. #define print(arr,xx) ;
  14. #define here
  15. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  16. #endif
  17. int caseno=0;
  18. #define print_case cout<<"Case "<<++caseno<<": ";
  19. #define fout freopen("output.txt","w",stdout);
  20. #define fin freopen("input.txt","r",stdin);
  21. #define pb push_back
  22. #define pi acos(-1.0)
  23. typedef long long ll;
  24. typedef pair<ll,ll> pll;
  25. typedef vector<vector<int> > vii;
  26. #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
  27. void yesno(bool okk) {cout<<(okk?"YES":"NO")<<endl;}
  28. const int primemod=1000000007;
  29. #define max(a, b) ((a) > (b) ? (a) : (b))
  30. #define min(a, b) ((a) < (b) ? (a) : (b))
  31. const ll maxsize = 3*100000+9; 
  32. #define fi first
  33. #define se second
  34. #define inf 1<<30
  35. const int N = 210;
  36. ll n;
  37. vector<vector<int>> adj;
  38. int capacity[N][N];
  39. int bfs(int s, int t, vector<int>&par){
  40.     fill(par.begin(), par.end(),-1);
  41.     par[s]=-2;
  42.     queue<pair<int,int>>q;
  43.     q.push({s,inf});
  44.     while(!q.empty()){
  45.         int cap = q.front().se;
  46.         int cur = q.front().fi;
  47.         q.pop();
  48.         for(auto next:adj[cur]){
  49.             if(par[next]==-1 and capacity[cur][next]>0){
  50.                 par[next]=cur;
  51.                 int flow = min(capacity[cur][next],cap);
  52.                 if(next==t)return flow;
  53.                 q.push({next,flow});
  54.             }
  55.         }
  56.     }
  57.     return 0;
  58. }
  59. int maxflow(int s,int t){
  60.     int flow  = 0,cur_fl;
  61.     vector<int>par(2*n+3);
  62.     while(cur_fl=bfs(s,t,par)){
  63.         flow += cur_fl;
  64.         int cur=t;
  65.         while(cur!=s){
  66.             int prev = par[cur];
  67.             capacity[cur][prev]+=cur_fl;
  68.             capacity[prev][cur]-=cur_fl;
  69.             cur = prev;
  70.         }
  71.     }
  72.     return flow;
  73. }
  74.  
  75. void solve(){
  76.     cin>>n;
  77.     for(int i=0;i<adj.size();i++)adj[i].clear();
  78.     adj.resize(2*n+2);
  79.     memset(capacity, 0, sizeof capacity);
  80.     for(int i=1;i<=n;i++){
  81.     	int x;
  82.         cin>>x;
  83.         adj[i].pb(i+n);
  84.         capacity[i][i+n]+=x;
  85.     }
  86.     int m;
  87.     cin>>m;
  88.     while(m--){
  89.         int i, j, k;
  90.         cin>>i>>j>>k;
  91.         adj[i+n].pb(j);
  92.         capacity[i+n][j]+=k;
  93.     }
  94.     int b,d;
  95.     cin>>b>>d;
  96.     while(b--){
  97.         int i;
  98.         cin>>i;
  99.         adj[0].pb(i);
  100.         capacity[0][i] = inf;
  101.     }
  102.     while(d--){
  103.         int i;
  104.         cin>>i;
  105.         adj[i+n].pb(2*n+1);
  106.         capacity[i+n][2*n+1] = inf;
  107.     }
  108.     cout<<maxflow(0,2*n+1)<<endl;
  109.  
  110. }
  111. int main(){
  112.     #ifndef ONLINE_JUDGE
  113.     fin
  114.     fout
  115.     #endif  
  116.     ///-----
  117.      fastio
  118.      int T;
  119.      T=1;
  120.      cin>>T;
  121.     while(T--){
  122.         // yesno(solve());
  123.         print_case
  124.         solve();
  125.     }
  126.     ///-----
  127.      return 0 ;
  128.  }
Success #stdin #stdout 0s 4520KB
comments (?)
stdin
copy 
2
4
10 20 30 40
6
1 2 5
1 3 10
1 4 13
2 3 5
2 4 7
3 4 20
3 1
1 2 3 4
2
50 100
1
1 2 100
1 1
1 2
stdout
copy 
Case 1: 37
Case 2: 50
https://ideone.com/e5ndtq
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!