bzoj3438: 小M的作物（那年花开最小割）

3438: 小M的作物

题解：
　　最小割标准水题（做了几天的最小割之后表示是真的水）
　　为什么水：博主已经做过两道基本一样的题目了...
　　详情参考：bzoj3894
代码：
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<cmath>
  5 #include<algorithm>
  6 #define N 510000
  7 #define inf 999999999
  8 #define qread(x)x=read();
  9 using namespace std;
 10 typedef long long LL;
 11 inline LL read()
 12 {
 13     LL f=1,x=0;char ch;
 14     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 15     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 16     return f*x;
 17 }
 18 struct node
 19 {
 20     int x,y,next,other;
 21     LL c;
 22 }a[N*2];int len,last[N];
 23 LL n,m,st,ed,head,tail;
 24 void ins(int x,int y,LL c)
 25 {
 26     int k1,k2;
 27     k1=++len;
 28     a[len].x=x;a[len].y=y;a[len].c=c;
 29     a[len].next=last[x];last[x]=len;
 30     
 31     k2=++len;
 32     a[len].x=y;a[len].y=x;a[len].c=0;
 33     a[len].next=last[y];last[y]=len;
 34     
 35     a[k1].other=k2;
 36     a[k2].other=k1;
 37 }
 38 int list[N],h[N];
 39 bool bt_h()
 40 {
 41     memset(h,0,sizeof(h));h[st]=1;
 42     list[1]=st;head=1;tail=2;
 43     while(head!=tail)
 44     {
 45         int x=list[head];
 46         for(int k=last[x];k;k=a[k].next)
 47         {
 48             int y=a[k].y;
 49             if(h[y]==0 && a[k].c>0)
 50             {
 51                 h[y]=h[x]+1;
 52                 list[tail++]=y;
 53             }
 54         }
 55         head++;
 56     }
 57     if(h[ed]>0)return true;
 58     return false;
 59 }
 60 int find_flow(int x,LL flow)
 61 {
 62     if(x==ed)return flow;
 63     LL s=0,t;
 64     for(int k=last[x];k;k=a[k].next)
 65     {
 66         int y=a[k].y;
 67         if(h[y]==h[x]+1 && a[k].c>0 && s<flow)
 68         {
 69             s+=t=find_flow(y,min(a[k].c,flow-s));
 70             a[k].c-=t;a[a[k].other].c+=t;
 71         }
 72     }
 73     if(s==0)h[x]=0;
 74     return s;
 75 }
 76 LL A[1100],B[1100],c1[1100],c2[11000];
 77 int main()
 78 {
 79     len=0;memset(last,0,sizeof(last));
 80     qread(n);
 81     LL sum=0;
 82     for(int i=1;i<=n;i++){qread(A[i]);sum+=A[i];}
 83     for(int i=1;i<=n;i++){qread(B[i]);sum+=B[i];}
 84     qread(m);st=N-2;ed=N-1;
 85     for(int i=1;i<=n;i++)
 86     {
 87         ins(st,i,A[i]);
 88         ins(i,ed,B[i]);
 89     }
 90     for(int i=1;i<=m;i++)
 91     {
 92         int k;qread(k);qread(c1[i]);qread(c2[i]);
 93         sum+=c1[i]+c2[i];ins(st,i+n,c1[i]);ins(i+n+m,ed,c2[i]);
 94         for(int j=1;j<=k;j++)
 95         {
 96             int x;qread(x);
 97             ins(i+n,x,inf);
 98             ins(x,i+n+m,inf);
 99         }
100     }
101     LL ans=0;
102     while(bt_h())ans+=find_flow(st,inf);
103     printf("%lld
",sum-ans);
104     return 0;
105 }