BZOJ 2127: happiness(最小割解決集合劃分)

Description

高一一班的座位表是個n*m的矩陣，經過一個學期的相處，每個同學和前後左右相鄰的同學互相成為了好朋友。這學期要分文理科了，每個同學對於選擇文科與理科有著自己的喜悅值，而一對好朋友如果能同時選文科或者理科，那麼他們又將收穫一些喜悅值。作為電腦競賽教練的scp大老闆，想知道如何分配可以使得全班的喜悅值總和最大。

Input

第一行兩個正整數n，m。接下來是六個矩陣第一個矩陣為n行m列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學選擇文科獲得的喜悅值。第二個矩陣為n行m列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學選擇理科獲得的喜悅值。第三個矩陣為n-1行m列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學與第i+1行第j列的同學同時選擇文科獲得的額外喜悅值。第四個矩陣為n-1行m列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學與第i+1行第j列的同學同時選擇理科獲得的額外喜悅值。第五個矩陣為n行m-1列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學與第i行第j+1列的同學同時選擇文科獲得的額外喜悅值。第六個矩陣為n行m-1列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學與第i行第j+1列的同學同時選擇理科獲得的額外喜悅值。

Output

輸出一個整數，表示喜悅值總和的最大值

Sample Input

Sample Output

HINT

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 using namespace std;
  7 const int MAXN=200001;
  8 const int INF = 1e8;
  9 inline void read(int &n)
 10 {
 11     char c='+';int x=0;bool flag=0;
 12     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 13     while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
 14     n=flag==1?-x:x;
 15 }
 16 int n,m,s,t;
 17 struct node
 18 {
 19     int u,v,flow,nxt;
 20 }edge[MAXN];
 21 int head[MAXN];
 22 int cur[MAXN];
 23 int num=0;
 24 int deep[MAXN];
 25 int tot=0;
 26 void add_edge(int x,int y,int z)
 27 {
 28     edge[num].u=x;
 29     edge[num].v=y;
 30     edge[num].flow=z;
 31     edge[num].nxt=head[x];
 32     head[x]=num++;
 33 }
 34 void add(int x,int y,int z)
 35 {
 36     add_edge(x,y,z);
 37     add_edge(y,x,0);
 38 }
 39 bool BFS()
 40 {
 41     memset(deep,0,sizeof(deep));
 42     deep[s]=1;
 43     queue<int>q;
 44     q.push(s);
 45     while(q.size()!=0)
 46     {
 47         int p=q.front();
 48         q.pop();
 49         for(int i=head[p];i!=-1;i=edge[i].nxt)
 50             if(!deep[edge[i].v]&&edge[i].flow)
 51                 deep[edge[i].v]=deep[edge[i].u]+1,
 52                 q.push(edge[i].v);
 53     }
 54     return deep[t];
 55     
 56 }
 57 int DFS(int now,int nowflow)
 58 {
 59     if(now==t||nowflow<=0)
 60         return nowflow;
 61     int totflow=0;
 62     for(int &i=cur[now];i!=-1;i=edge[i].nxt)
 63     {
 64         if(deep[edge[i].v]==deep[edge[i].u]+1&&edge[i].flow)
 65         {
 66             int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow));
 67             edge[i].flow-=canflow;
 68             edge[i^1].flow+=canflow;
 69             totflow+=canflow;
 70             nowflow-=canflow;
 71             if(nowflow<=0)
 72                 break;
 73         }
 74     
 75     }
 76     return totflow;
 77 }
 78 void Dinic()
 79 {
 80     int ans=0;
 81     while(BFS())
 82     {
 83         memcpy(cur,head,MAXN);
 84         ans+=DFS(s,1e8);
 85     }
 86     printf("%d",tot-(ans>>1));
 87 }
 88 int a[101][101];
 89 int b[101][101];
 90 int mark[101][101];
 91 int main()
 92 {
 93     int n,m;
 94     read(n);read(m);
 95     s=0;t=10001;
 96     memset(head,-1,sizeof(head));
 97     for(int i=1;i<=n;i++)
 98         for(int j=1;j<=m;j++)
 99             cin>>a[i][j],tot+=a[i][j],a[i][j]<<=1;
100     for(int i=1;i<=n;i++)
101         for(int j=1;j<=m;j++)
102             cin>>b[i][j],tot+=b[i][j],b[i][j]<<=1;
103     for(int i=1;i<=n;i++)
104         for(int j=1;j<=m;j++)
105             mark[i][j]=((i-1)*m+j);
106     for(int i=1;i<=n-1;i++)
107         for(int j=1;j<=m;j++)
108         {
109             int p;cin>>p;tot+=p;
110             a[i][j]+=p,a[i+1][j]+=p;
111             add_edge(mark[i][j],mark[i+1][j],p);
112             add_edge(mark[i+1][j],mark[i][j],p);
113         }
114     for(int i=1;i<=n-1;i++)
115         for(int j=1;j<=m;j++)
116         {
117             int p;cin>>p;tot+=p;
118             b[i][j]+=p,b[i+1][j]+=p;
119             add_edge(mark[i][j],mark[i+1][j],p);
120             add_edge(mark[i+1][j],mark[i][j],p);
121         }
122     for(int i=1;i<=n;i++)
123         for(int j=1;j<=m-1;j++)
124         {
125             int p;cin>>p;tot+=p;
126             a[i][j]+=p,a[i][j+1]+=p;
127             add_edge(mark[i][j],mark[i][j+1],p);
128             add_edge(mark[i][j+1],mark[i][j],p);
129         }
130     for(int i=1;i<=n;i++)
131         for(int j=1;j<=m-1;j++)
132         {
133             int p;cin>>p;tot+=p;
134             b[i][j]+=p,b[i][j+1]+=p;
135             add_edge(mark[i][j],mark[i][j+1],p);
136             add_edge(mark[i][j+1],mark[i][j],p);
137         }
138     for(int i=1;i<=n;i++)
139         for(int j=1;j<=m;j++)
140         {
141             add(0,mark[i][j],a[i][j]);
142             add(mark[i][j],t,b[i][j]);
143         }
144     Dinic();
145     return  0;
146 }