bzoj2127: happiness（双倍经验最小割）

2127: happiness

题目：传送门

题解：

　　 双倍经验美滋滋~

　　 请看蒟蒻以前写的渣题解...bzoj3894

　　 表示做完自己就最小割了...

代码（直接改的...菜啊）：

　

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #define inf 999999999

 #define qread(x)x=read();

 using namespace std;

 inline int read()

 {

     int f=,x=;char ch;

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return f*x;

 }

 const int dx[]={,-,,,};

 const int dy[]={,,,-,};

 struct node

 {

     int x,y,c,next,other;

 }a[];int len,last[];

 int n,m,st,ed,head,tail;

 void ins(int x,int y,int c)

 {

     int k1,k2;

     k1=++len;

     a[len].x=x;a[len].y=y;a[len].c=c;

     a[len].next=last[x];last[x]=len;

     k2=++len;

     a[len].x=y;a[len].y=x;a[len].c=;

     a[len].next=last[y];last[y]=len;

     a[k1].other=k2;

     a[k2].other=k1;

 }

 int list[],h[];

 bool bt_h()

 {

     memset(h,,sizeof(h));h[st]=;

     list[]=st;head=;tail=;

     while(head!=tail)

     {

         int x=list[head];

         for(int k=last[x];k;k=a[k].next)

         {

             int y=a[k].y;

             if(h[y]== && a[k].c>)

             {

                 h[y]=h[x]+;

                 list[tail++]=y;

             }

         }

         head++;

     }

     if(h[ed]>)return true;

     return false;

 }

 int find_flow(int x,int flow)

 {

     if(x==ed)return flow;

     int s=,t;

     for(int k=last[x];k;k=a[k].next)

     {

         int y=a[k].y;

         if(h[y]==h[x]+ && a[k].c> && s<flow)

         {

             s+=t=find_flow(y,min(a[k].c,flow-s));

             a[k].c-=t;a[a[k].other].c+=t;

         }

     }

     if(s==)h[x]=;

     return s;

 }

 int w[][],l[][],sw1[][],sl1[][],sw2[][],sl2[][];

 int d[][];

 int main()

 {

     qread(n);qread(m);

     st=n*m*+;ed=st+;

     len=;memset(last,,sizeof(last));

     int ss=;

     for(int i=;i<=n;i++)for(int j=;j<=m;j++)d[i][j]=ss++;

     int sum=;

     for(int i=;i<=n;i++)for(int j=;j<=m;j++){qread(w[i][j]);ins(st,d[i][j],w[i][j]);sum+=w[i][j];}

     for(int i=;i<=n;i++)for(int j=;j<=m;j++){qread(l[i][j]);ins(d[i][j],ed,l[i][j]);sum+=l[i][j];}

     for(int i=;i<n;i++)

         for(int j=;j<=m;j++)

         {

             qread(sw1[i][j]);

             if(d[i][j]>)

                 ins(d[i][j]+n*m,d[i][j],inf);

             if(d[i+][j]>)

                 ins(d[i][j]+n*m,d[i+][j],inf);

             ins(st,d[i][j]+n*m,sw1[i][j]);

             sum+=sw1[i][j];

         }

     for(int i=;i<n;i++)

         for(int j=;j<=m;j++)

         {

             qread(sl1[i][j]);

             if(d[i][j]>)

                 ins(d[i][j],d[i][j]+n*m*,inf);

             if(d[i+][j]>)

                 ins(d[i+][j],d[i][j]+n*m*,inf);

             ins(d[i][j]+n*m*,ed,sl1[i][j]);

             sum+=sl1[i][j];

         }

     for(int i=;i<=n;i++)

         for(int j=;j<m;j++)

         {

             qread(sw2[i][j]);

             if(d[i][j]>)

                 ins(d[i][j]+n*m*,d[i][j],inf);

             if(d[i][j+]>)

                 ins(d[i][j]+n*m*,d[i][j+],inf);

             ins(st,d[i][j]+n*m*,sw2[i][j]);

             sum+=sw2[i][j];

         }

     for(int i=;i<=n;i++)

         for(int j=;j<m;j++)

         {

             qread(sl2[i][j]);

             if(d[i][j]>)

                 ins(d[i][j],d[i][j]+n*m*,inf);

             if(d[i][j+]>)

                 ins(d[i][j+],d[i][j]+n*m*,inf);

             ins(d[i][j]+n*m*,ed,sl2[i][j]);

             sum+=sl2[i][j];

         }

     int ans=;

     while(bt_h())ans+=find_flow(st,inf);

     printf("%d\n",sum-ans);

     return ;

 }