yicongli

Gym 313459G

Jan 24th, 2021
541
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=10005;
  17. const int M=100005;
  18. const int INF=(1ull<<31)-1;
  19.  
  20. namespace Dinic{
  21.  
  22.     int n,s,t,ecnt=1;
  23.     int fir[N],cur[N],dep[N],nex[M<<1],to[M<<1],w[M<<1];
  24.  
  25.     inline void addedge(int u,int v,int c){
  26.         nex[++ecnt]=fir[u],fir[u]=ecnt,to[ecnt]=v,w[ecnt]=c;
  27.         nex[++ecnt]=fir[v],fir[v]=ecnt,to[ecnt]=u,w[ecnt]=0;
  28.     }
  29.  
  30.     inline bool bfs(){
  31.         memset(dep,0,n<<2);
  32.         memcpy(cur,fir,n<<2);
  33.         dep[s]=1;
  34.         queue<int>Q;
  35.         Q.push(s);
  36.         while(!Q.empty()){
  37.             int x=Q.front();
  38.             Q.pop();
  39.             for(int i=fir[x];i;i=nex[i]){
  40.                 int v=to[i];
  41.                 if(dep[v]||!w[i])continue;
  42.                 dep[v]=dep[x]+1;
  43.                 if(v==t)return 1;
  44.                 Q.push(v);
  45.             }
  46.         }
  47.         return 0;
  48.     }
  49.  
  50.     int dfs(int x,int lim){
  51.         if(x==t||!lim)return lim;
  52.         int flow=0;
  53.         for(int &i=cur[x],f;i&&lim;i=nex[i]){
  54.             int v=to[i];
  55.             if((dep[v]==dep[x]+1)&&(f=dfs(v,min(lim,w[i])))){
  56.                 if(f){
  57.                     w[i]-=f;
  58.                     w[i^1]+=f;
  59.                     flow+=f;
  60.                     lim-=f;
  61.                 }
  62.             }
  63.         }
  64.         return flow;
  65.     }
  66.  
  67.     inline int dinic(){
  68.         int Ans=0;
  69.         while(bfs()){
  70.             Ans+=dfs(s,INF);
  71.         }
  72.         return Ans;
  73.     }
  74. }
  75. int main(){
  76.     // freopen(".in","r",stdin);
  77.     // freopen(".out","w",stdout);
  78.     int sum=0;
  79.     int n;r(n);
  80.     Dinic::t=0;
  81.     for(int i=1;i<=n;++i){
  82.         int v,f;r(v),r(f);
  83.         Dinic::addedge(i,Dinic::t,v);
  84.         sum+=v*f;
  85.     }
  86.     int m;r(m);
  87.     Dinic::s=n+m+1;
  88.     Dinic::n=n+m+2;
  89.     for(int i=n+1;i<=n+m;++i){
  90.         int c,v;r(c),r(v);
  91.         Dinic::addedge(Dinic::s,i,v);
  92.         for(int j=1;j<=c;++j){
  93.             int x;r(x);
  94.             Dinic::addedge(i,x,INF);
  95.         }
  96.         sum+=v;
  97.     }
  98.     printf("%d\n",sum-Dinic::dinic());
  99.     return 0;
  100. }
RAW Paste Data