题意：有一个n*m的矩阵，里面可以放金蛋也可以放银蛋。分别给出在2个矩阵map1,map2表示在矩阵的每个格子里放金蛋的得分和放银蛋的得分。如果相邻的两个格子里都放了金蛋，则总得分要减去G，如果相邻的两个格子里都放了银蛋，则总得分要减去S。现要求你求出放蛋的最大得分。
跟HDU 3657比较像，但是这里更加复杂了，因为两种得分，一种金蛋，一种银蛋。所以我的理解是这里是两个二分图合起来的一个二分图，因为金蛋和银蛋存在一个匹配的关系，给矩阵染色后，黑格和白格也存在一个匹配的关系。因此，这样建图：假设行数i+列数j这和为偶数的格子为黑格，奇数的为白格，每个格子拆成两个点k,k'，分别表示放金蛋还是放银蛋，所以图中一共有2*n*m+2个点。
建图的方法大概是这样的：
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define INF 1<<30 6 #define maxn 5010 7 #define maxm 100000 8 using namespace std; 9 10 int v[maxm],next[maxm],w[maxm]; 11 int first[maxn],d[maxn],work[maxn],q[maxn]; 12 int e,S,T; 13 int n,m,gold,silver; 14 int map1[55][55],map2[55][55]; 15 void init(){ 16 e = 0; 17 memset(first,-1,sizeof(first)); 18 } 19 20 void add_edge(int a,int b,int c){ 21 //printf("add:%d to %d,cap = %d ",a,b,c); 22 v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++; 23 v[e] = a;next[e] = first[b];w[e] = 0;first[b] = e++; 24 } 25 26 int bfs(){ 27 int rear = 0; 28 memset(d,-1,sizeof(d)); 29 d[S] = 0;q[rear++] = S; 30 for(int i = 0;i < rear;i++){ 31 for(int j = first[q[i]];j != -1;j = next[j]) 32 if(w[j] && d[v[j]] == -1){ 33 d[v[j]] = d[q[i]] + 1; 34 q[rear++] = v[j]; 35 if(v[j] == T) return 1; 36 } 37 } 38 return 0; 39 } 40 41 int dfs(int cur,int a){ 42 if(cur == T) return a; 43 for(int &i = work[cur];i != -1;i = next[i]){ 44 if(w[i] && d[v[i]] == d[cur] + 1) 45 if(int t = dfs(v[i],min(a,w[i]))){ 46 w[i] -= t;w[i^1] += t; 47 return t; 48 } 49 } 50 return 0; 51 } 52 53 int dinic(){ 54 int ans = 0; 55 while(bfs()){ 56 memcpy(work,first,sizeof(first)); 57 while(int t = dfs(S,INF)) ans += t; 58 } 59 return ans; 60 } 61 62 int main() 63 { 64 int nkase; 65 scanf("%d",&nkase); 66 for(int kase = 1;kase <= nkase;kase++){ 67 scanf("%d%d%d%d",&n,&m,&gold,&silver); 68 S = 0,T = 2*n*m+1; 69 init(); 70 int sum = 0,k = n*m; 71 for(int i = 1;i <= n;i++){ 72 for(int j = 1;j <= m;j++) 73 scanf("%d",&map1[i][j]),sum += map1[i][j]; 74 } 75 for(int i = 1;i <= n;i++){ 76 for(int j = 1;j <= m;j++) 77 scanf("%d",&map2[i][j]),sum += map2[i][j]; 78 } 79 for(int i = 1;i <= n;i++){ 80 for(int j = 1;j <= m;j++){ 81 int pos = (i-1)*m+j; 82 if((i+j)%2 == 1){ 83 add_edge(S,pos,map1[i][j]); 84 add_edge(pos+k,T,map2[i][j]); 85 add_edge(pos,pos+k,INF); 86 if(i > 1) add_edge(pos,pos-m,gold); 87 if(i < n) add_edge(pos,pos+m,gold); 88 if(j > 1) add_edge(pos,pos-1,gold); 89 if(j < m) add_edge(pos,pos+1,gold); 90 }else{ 91 add_edge(S,pos+k,map2[i][j]); 92 add_edge(pos,T,map1[i][j]); 93 add_edge(pos+k,pos,INF); 94 if(i > 1) add_edge(pos+k,pos+k-m,silver); 95 if(i < n) add_edge(pos+k,pos+k+m,silver); 96 if(j > 1) add_edge(pos+k,pos+k-1,silver); 97 if(j < m) add_edge(pos+k,pos+k+1,silver); 98 } 99 } 100 } 101 printf("Case %d: %d ",kase,sum-dinic()); 102 } 103 return 0; 104 }