Description
文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠
结过）
小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行
描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择
一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式
得到：
1．如果第i行第秒J的同学选择了文科，则他将获得art[i][j]的满意值，如
果选择理科，将得到science[i][j]的满意值。
2．如果第i行第J列的同学选择了文科，并且他相邻（两个格子相邻当且
仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开
心，所以会增加same_art[i][j]的满意值。
3．如果第i行第j列的同学选择了理科，并且他相邻的同学全部选择了理
科，则增加same_science[i]j[]的满意值。
小P想知道，大家应该如何选择，才能使所有人的满意值之和最大。请
告诉他这个最大值。
Input
第一行为两个正整数：n，m
接下来n术m个整数，表示art[i][j]；
接下来n术m个整数．表示science[i][j]；
接下来n术m个整数，表示same_art[i][j]；
Output
输出为一个整数，表示最大的满意值之和
Sample Input
3 4
13 2 4 13
7 13 8 12
18 17 0 5
13 2 4 13
7 13 8 12
18 17 0 5
8 13 15 4
11 3 8 11
11 18 6 5
1 2 3 4
4 2 3 2
3 1 0 4
3 2 3 2
0 2 2 1
0 2 4 4
Sample Output
152
HINT
样例说明
1表示选择文科，0表示选择理科，方案如下：
1 0 0 1
0 1 0 0
1 0 0 0
满意zhi
N,M<=100,读入数据均<=500
Solution
最小割，一个人要么选文科要么选理科。
如果周围的人和他同选文科（或理科）那么他会更开心，所以就新加一个点，将这个点连向S代表选文科（或T代表理科），权值为满意值，再将自己和周围的同学所代表的点连向这个点，并且权值无限大，因为不可能他自己或周围的人不选文科（或理科）却得到了周围的人同选文科（或理科）的满意值。
|
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 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int N=50000,M=1000000,dx[5]={0,0,0,-1,1},dy[5]={0,-1,1,0,0}; int n,m,S,T,tot,Next[M],head[N],tree[M],val[M],Queue[N],h[N],cur[N]; inline int calc(int x,int y) { return (x-1)*m+y;} void add(int x,int y,int z) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; } void add_edge(int x,int y,int z) { add(x,y,z); add(y,x,0); } bool bfs() { int t=0,w=1; memset(h,-1,sizeof(h)); Queue[1]=S;h[S]=0; while (t!=w) { int u=Queue[++t]; for (int i=head[u];i;i=Next[i]) if (val[i]!=0) { int v=tree[i]; if (h[v]==-1) { Queue[++w]=v; h[v]=h[u]+1; } } } return h[T]!=-1; } int dfs(int u,int low) { if (u==T) return low; int used=0; for (int i=cur[u];i;i=Next[i]) { cur[u]=i; int v=tree[i]; if (val[i]>0&&h[v]==h[u]+1) { int w=dfs(v,min(val[i],low-used)); val[i]-=w;val[i^1]+=w; used+=w; if (used==low) return low; } } if (used==0) h[u]=-1; return used; } int dinic() { int ans=0; while (bfs()) { for (int i=1;i<=T;i++) cur[i]=head[i]; ans+=dfs(S,1<<29); } return ans; } int main() { scanf("%d%d",&n,&m); tot=1; S=n*m*3+1;T=n*m*3+2; int sum=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { int x; scanf("%d",&x); add_edge(S,calc(i,j),x); sum+=x; } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { int x; scanf("%d",&x); add_edge(calc(i,j),T,x); sum+=x; } int now=n*m; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { int x; scanf("%d",&x); sum+=x; now++; for (int k=0;k<=4;k++) { int i1=i+dx[k],j1=j+dy[k]; if (i1<1||j1<1||i1>n||j1>m) continue; add_edge(now,calc(i1,j1),1<<29); } add_edge(S,now,x); } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { int x; scanf("%d",&x); sum+=x; now++; for (int k=0;k<=4;k++) { int i1=i+dx[k],j1=j+dy[k]; if (i1<1||j1<1||i1>n||j1>m) continue; add_edge(calc(i1,j1),now,1<<29); } add_edge(now,T,x); } printf("%d\n",sum-dinic()); return 0; } |
