「BZOJ2127」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
1 1
100 110
1
1000
Sample Output
「样例说明」
两人都选理，则获得100+110+1000的喜悦值。
「数据规模」
对于100%以内的数据，n,m<=100 所有喜悦值均为小于等于5000的非负整数
题解
利用最小割考虑。
对于原图中所有相邻的两个人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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
#include<iostream> #include<cstring> #include<cstdio> #define T 10001 #define inf 0x7fffffff #define FOR for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) #define rep(x,y) for(int i=1;i<=x;i++)for(int j=1;j<=y;j++) #define ll long long using namespace std; int n,m,ans,tot,cnt=1,head[10002],h[10002]; int a[101][101],b[101][101],color[101][101],mark[101][101]; int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; struct data{int to,next,v;}e[300001]; void ins(int u,int v,int w) {cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;} void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,0);} void ins2(int u,int v,int w) {ins(u,v,w);ins(v,u,w);} bool bfs() { int q[10005],t=0,w=1,i,now; memset(h,-1,sizeof(h)); q[0]=h[0]=0; while(t!=w) { now=q[t];t++;if(t==10001)t=0; for(i=head[now];i;i=e[i].next) { if(e[i].v&&h[e[i].to]<0) {h[e[i].to]=h[now]+1;q[w++]=e[i].to;if(w==10001)w=0;} } } if(h[T]==-1)return 0;return 1; } int dfs(int x,int f) { if(x==T)return f; int w,used=0; for(int i=head[x];i;i=e[i].next) { if(e[i].v&&h[e[i].to]==h[x]+1) { w=f-used; w=dfs(e[i].to,min(w,e[i].v)); e[i].v-=w;e[i^1].v+=w; used+=w;if(used==f)return f; } } if(!used)h[x]=-1; return used; } void dinic(){while(bfs())ans+=dfs(0,inf);} void build() { int x; rep(n-1,m) { scanf("%d",&x);tot+=x; a[i][j]+=x;a[i+1][j]+=x; ins2(mark[i][j],mark[i+1][j],x); } rep(n-1,m) { scanf("%d",&x);tot+=x; b[i][j]+=x;b[i+1][j]+=x; ins2(mark[i][j],mark[i+1][j],x); } rep(n,m-1) { scanf("%d",&x);tot+=x; a[i][j]+=x;a[i][j+1]+=x; ins2(mark[i][j],mark[i][j+1],x); } rep(n,m-1) { scanf("%d",&x);tot+=x; b[i][j]+=x;b[i][j+1]+=x; ins2(mark[i][j],mark[i][j+1],x); } FOR{ insert(0,mark[i][j],a[i][j]); insert(mark[i][j],T,b[i][j]); } } int main() { scanf("%d%d",&n,&m); FOR scanf("%d",&a[i][j]),tot+=a[i][j],a[i][j]<<=1; FOR scanf("%d",&b[i][j]),tot+=b[i][j],b[i][j]<<=1; FOR mark[i][j]=(i-1)*m+j; build();dinic(); printf("%d",tot-(ans>>1)); return 0; } |
OI 课件=>
[…] 题解： 最小割。。。 不会做。。。 这里Orz一下黄学长的题解：http://hzwer.com/2422.html […]