fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define int long long
  5. using namespace std;
  6. const long long oo=1e18;
  7. const int mod=1e9+7;
  8. const int base=31;
  9. int Test=1;
  10. bool bit(int mask,int i){return (mask>>i)&1;}
  11. void home()
  12. {
  13.     if(fopen("main.inp","r")) 
  14.     freopen("main.inp","r",stdin),
  15.     freopen("main.out","w",stdout);
  16. }
  17. int n,m,s,t,sum;
  18. vector<int>a[5005];
  19. int f[5005][5005],c[5005][5005];
  20. int val[5005],d[5005],curId[5005];
  21. bool BFS()
  22. {
  23.     fill(d+s,d+t+1,oo);
  24.     queue<int>q;q.push(s);d[s]=0;
  25.     while(!q.empty())
  26.     {
  27.         int u=q.front();q.pop();
  28.         for(int v:a[u])
  29.         {
  30.             if(d[v]==oo&&f[u][v]<c[u][v])
  31.                 q.push(v),d[v]=d[u]+1;
  32.         }
  33.     }
  34.     return d[t]!=oo;
  35. }
  36. int DFS(int u,int curFlow)
  37. {
  38.     if(u==t||(!curFlow))return curFlow;
  39.     if(d[u]>=d[t])return 0; 
  40.     for(;curId[u]<a[u].size();curId[u]++)
  41.     {
  42.         int v=a[u][curId[u]];
  43.         if(d[v]!=d[u]+1)continue;
  44.         int newFlow=DFS(v,min(curFlow,c[u][v]-f[u][v]));
  45.         if(!newFlow)continue;
  46.         f[u][v]+=newFlow;
  47.         f[v][u]-=newFlow;
  48.         return newFlow;
  49.     }
  50.     return 0;
  51. }
  52. int Dinic()
  53. {
  54.     int maxFlow=0;
  55.     while(BFS())
  56.     {
  57.         memset(curId,0,sizeof(curId));
  58.         int newFlow=0;
  59.         while(newFlow=DFS(s,oo))
  60.             maxFlow+=newFlow;
  61.     }
  62.     return maxFlow;
  63. }
  64. void Tcmduc_VOI26()
  65. {
  66.     cin>>n>>m;s=0,t=n+m+1;
  67.     for(int i=0;i<=t;i++)
  68.     {
  69.         a[i].clear();
  70.         fill(f[i],f[i]+t+1,0);
  71.         fill(c[i],c[i]+t+1,0);
  72.     }
  73.     sum=0;
  74.     for(int i=1;i<=n;i++)
  75.     {
  76.         cin>>val[i];sum+=val[i];
  77.         c[m+i][t]=val[i];
  78.         a[m+i].push_back(t);
  79.         a[t].push_back(m+i);
  80.     }
  81.     for(int i=1;i<=m;i++)
  82.     {
  83.         int x;cin>>x;c[0][i]=x;
  84.         a[0].push_back(i);
  85.         a[i].push_back(0);
  86.     }
  87.     for(int i=1;i<=m;i++)
  88.     {
  89.         int k;cin>>k;
  90.         while(k--)
  91.         {
  92.             int id;cin>>id;
  93.             c[i][m+id]=val[id];
  94.             a[i].push_back(m+id);
  95.             a[m+id].push_back(i);
  96.         }
  97.     }
  98.     cout<<sum-Dinic()<<'\n';
  99. }
  100. signed main()
  101. {
  102.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);home();
  103.     cin>>Test;while(Test--)Tcmduc_VOI26();
  104.     return 0;
  105. }
  106.  
Success #stdin #stdout 0.01s 7792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/kH0B3q
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

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!