BZOJ 2127: happiness(最小割解决集合划分) _最小割

努力尽今夕，少年犹可夸。这篇文章主要讲述BZOJ 2127: happiness(最小割解决集合划分)相关的知识，希望能为你提供帮助。
Time Limit: 51 Sec Memory Limit: 259 MB
Submit: 2350 Solved: 1138
[Submit][Status][Discuss] 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 1 2
1 1
100 110
1
1000
Sample Output 1210
【样例说明】
两人都选理，则获得100+110+1000的喜悦值。
【数据规模】
对于100%以内的数据，n,m< =100所有喜悦值均为小于等于5000的非负整数
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 { 11char c=\'+\'; int x=0; bool flag=0; 12while(c< \'0\'||c> \'9\'){c=getchar(); if(c==\'-\')flag=1; } 13while(c> =\'0\'& & c< =\'9\'){x=x*10+c-48; c=getchar(); } 14n=flag==1?-x:x; 15 } 16 int n,m,s,t; 17 struct node 18 { 19int 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 { 28edge[num].u=x; 29edge[num].v=y; 30edge[num].flow=z; 31edge[num].nxt=head[x]; 32head[x]=num++; 33 } 34 void add(int x,int y,int z) 35 { 36add_edge(x,y,z); 37add_edge(y,x,0); 38 } 39 bool BFS() 40 { 41memset(deep,0,sizeof(deep)); 42deep[s]=1; 43queue< int> q; 44q.push(s); 45while(q.size()!=0) 46{ 47int p=q.front(); 48q.pop(); 49for(int i=head[p]; i!=-1; i=edge[i].nxt) 50if(!deep[edge[i].v]& & edge[i].flow) 51deep[edge[i].v]=deep[edge[i].u]+1, 52q.push(edge[i].v); 53} 54return deep[t]; 55 56 } 57 int DFS(int now,int nowflow) 58 { 59if(now==t||nowflow< =0) 60return nowflow; 61int totflow=0; 62for(int & i=cur[now]; i!=-1; i=edge[i].nxt) 63{ 64if(deep[edge[i].v]==deep[edge[i].u]+1& & edge[i].flow) 65{ 66int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow)); 67edge[i].flow-=canflow; 68edge[i^1].flow+=canflow; 69totflow+=canflow; 70nowflow-=canflow; 71if(nowflow< =0) 72break; 73} 74 75} 76return totflow; 77 } 78 void Dinic() 79 { 80int ans=0; 81while(BFS()) 82{ 83memcpy(cur,head,MAXN); 84ans+=DFS(s,1e8); 85} 86printf("%d",tot-(ans> > 1)); 87 } 88 int a[101][101]; 89 int b[101][101]; 90 int mark[101][101]; 91 int main() 92 { 93int n,m; 94read(n); read(m); 95s=0; t=10001; 96memset(head,-1,sizeof(head)); 97for(int i=1; i< =n; i++) 98for(int j=1; j< =m; j++) 99cin> > a[i][j],tot+=a[i][j],a[i][j]< < =1; 100for(int i=1; i< =n; i++) 101for(int j=1; j< =m; j++) 102cin> > b[i][j],tot+=b[i][j],b[i][j]< < =1; 103for(int i=1; i< =n; i++) 104for(int j=1; j< =m; j++) 105mark[i][j]=((i-1)*m+j); 106for(int i=1; i< =n-1; i++) 107for(int j=1; j< =m; j++) 108{ 109int p; cin> > p; tot+=p; 110a[i][j]+=p,a[i+1][j]+=p; 111add_edge(mark[i][j],mark[i+1][j],p); 112add_edge(mark[i+1][j],mark[i][j],p); 113} 114for(int i=1; i< =n-1; i++) 115for(int j=1; j< =m; j++) 116{ 117int p; cin> > p; tot+=p; 118b[i][j]+=p,b[i+1][j]+=p; 119add_edge(mark[i][j],mark[i+1][j],p); 120add_edge(mark[i+1][j],mark[i][j],p); 121} 122for(int i=1; i< =n; i++) 123for(int j=1; j< =m-1; j++) 124{ 125int p; cin> > p; tot+=p; 126a[i][j]+=p,a[i][j+1]+=p; 127add_edge(mark[i][j],mark[i][j+1],p); 128add_edge(mark[i][j+1],mark[i][j],p); 129} 130for(int i=1; i< =n; i++) 131for(int j=1; j< =m-1; j++) 132{ 133int p; cin> > p; tot+=p; 134b[i][j]+=p,b[i][j+1]+=p; 135add_edge(mark[i][j],mark[i][j+1],p); 136add_edge(mark[i][j+1],mark[i][j],p); 137} 138for(int i=1; i< =n; i++) 139for(int j=1; j< =m; j++) 140{ 141add(0,mark[i][j],a[i][j]); 142add(mark[i][j],t,b[i][j]); 143} 144Dinic(); 145return0; 146 }

【BZOJ 2127: happiness(最小割解决集合划分)】