bzoj2127happiness 最大流 _最大流

采得百花成蜜后，为谁辛苦为谁甜。这篇文章主要讲述bzoj2127happiness 最大流相关的知识，希望能为你提供帮助。
happinessTime Limit: 51 Sec Memory Limit: 259 MB
Submit: 2579 Solved: 1245
[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和文理分科差不多
利用最小割考虑。
对于原图中所有相邻的两个人A，B，我们建边：
s-> A:cost[A文]+c[文][A][B]/2,s-> B:cost[B文]+c[文][A][B]/2;
A-> t:cost[A理]+c[理][A][B]/2,B-> t:costB[理]+c[理][A][B]/2;
A< – > B:c[文][A][B]/2+c[理][A][B]/2
这样会出现两种割，分别对应两种相同，一种选文一种选理。

1 #include< iostream> 2 #include< cstring> 3 #include< cstdio> 4 #define T 10001 5 #define inf 0x7fffffff 6 #define FOR for(int i=1; i< =n; i++)for(int j=1; j< =m; j++) 7 #define rep(x,y) for(int i=1; i< =x; i++)for(int j=1; j< =y; j++) 8 #define ll long long 9 using namespace std; 10 int n,m,ans,tot,cnt=1,head[10002],h[10002]; 11 int a[101][101],b[101][101],color[101][101],mark[101][101]; 12 int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; 13 struct data{int to,next,v; }e[300001]; 14 void ins(int u,int v,int w) 15 {cnt++; e[cnt].to=v; e[cnt].v=w; e[cnt].next=head[u]; head[u]=cnt; } 16 void insert(int u,int v,int w) 17 {ins(u,v,w); ins(v,u,0); } 18 void ins2(int u,int v,int w) 19 {ins(u,v,w); ins(v,u,w); } 20 bool bfs() 21 { 22int q[10005],t=0,w=1,i,now; 23memset(h,-1,sizeof(h)); 24q[0]=h[0]=0; 25while(t!=w) 26{ 27now=q[t]; t++; if(t==10001)t=0; 28for(i=head[now]; i; i=e[i].next) 29{ 30if(e[i].v& & h[e[i].to]< 0) 31{h[e[i].to]=h[now]+1; q[w++]=e[i].to; if(w==10001)w=0; } 32} 33} 34if(h[T]==-1)return 0; return 1; 35} 36 int dfs(int x,int f) 37 { 38if(x==T)return f; 39int w,used=0; 40for(int i=head[x]; i; i=e[i].next) 41{ 42if(e[i].v& & h[e[i].to]==h[x]+1) 43{ 44w=f-used; 45w=dfs(e[i].to,min(w,e[i].v)); 46e[i].v-=w; e[i^1].v+=w; 47used+=w; if(used==f)return f; 48} 49} 50if(!used)h[x]=-1; 51return used; 52} 53 void dinic(){while(bfs())ans+=dfs(0,inf); } 54 void build() 55 { 56int x; 57rep(n-1,m) 58{ 59scanf("%d",& x); tot+=x; 60a[i][j]+=x; a[i+1][j]+=x; 61ins2(mark[i][j],mark[i+1][j],x); 62} 63rep(n-1,m) 64{ 65scanf("%d",& x); tot+=x; 66b[i][j]+=x; b[i+1][j]+=x; 67ins2(mark[i][j],mark[i+1][j],x); 68} 69rep(n,m-1) 70{ 71scanf("%d",& x); tot+=x; 72a[i][j]+=x; a[i][j+1]+=x; 73ins2(mark[i][j],mark[i][j+1],x); 74} 75rep(n,m-1) 76{ 77scanf("%d",& x); tot+=x; 78b[i][j]+=x; b[i][j+1]+=x; 79ins2(mark[i][j],mark[i][j+1],x); 80} 81FOR{ 82insert(0,mark[i][j],a[i][j]); 83insert(mark[i][j],T,b[i][j]); 84} 85 } 86 int main() 87 { 88scanf("%d%d",& n,& m); 89FOR scanf("%d",& a[i][j]),tot+=a[i][j],a[i][j]< < =1; 90FOR scanf("%d",& b[i][j]),tot+=b[i][j],b[i][j]< < =1; 91FOR mark[i][j]=(i-1)*m+j; 92build(); dinic(); 93printf("%d",tot-(ans> > 1)); 94 }

【bzoj2127happiness 最大流】