高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。
高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。
第一行两个正整数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列的同学同时选择理科获得的额外喜悦值。
输出一个整数，表示喜悦值总和的最大值
对于原图中所有相邻的两个人A，B，我们建边：（S源，T汇）
S->A:文A+文AB/2
S->B:文B+文AB/2
A->T:理A+理AB/2
B->T:理B+理AB/2
A<–>B:文AB/2+理AB/2
但是，为了保持精度准确，我们先建图时所有边*2，最后ans再/2.
1 #include<iostream> 2 #include<fstream> 3 #include<cstdio> 4 #include<algorithm> 5 #include<string> 6 #include<vector> 7 #include<queue> 8 #include<deque> 9 #include<utility> 10 #include<map> 11 #include<set> 12 #include<cmath> 13 #include<cstdlib> 14 #include<ctime> 15 #include<functional> 16 #include<sstream> 17 #include<cstring> 18 #include<bitset> 19 #include<stack> 20 using namespace std; 21 22 int n,m,s,t,cnt,x,y,z,sum; 23 struct sdt 24 { 25 int cap,flow,u,v; 26 }e[500005]; 27 int nxt[500005],fir[10005],d[10005],par[10005],num[10005],cur[10005]; 28 int wk[105][105],lk[105][105],kkk[105][105]; 29 bool vis[10005]; 30 31 int read() 32 { 33 int x=0;char c=getchar(); 34 while(c<48||c>57)c=getchar(); 35 while(c>47&&c<58)x*=10,x+=c-48,c=getchar(); 36 return x; 37 } 38 39 void add(int x,int y,int z) 40 { 41 e[++cnt].u=x;e[cnt].v=y;e[cnt].cap=z;e[cnt].flow=0; 42 nxt[cnt]=fir[x];fir[x]=cnt; 43 } 44 45 void bfs() 46 { 47 memset(vis,0,sizeof(vis)); 48 memset(d,0,sizeof(d)); 49 queue<int>q; 50 d[t]=0; 51 vis[t]=1; 52 q.push(t); 53 while(!q.empty()) 54 { 55 int k=q.front(); 56 q.pop(); 57 for(int i=fir[k];i;i=nxt[i]) 58 { 59 if(!vis[e[i].v] && e[i].cap==0) 60 { 61 vis[e[i].v]=1; 62 d[e[i].v]=d[k]+1; 63 q.push(e[i].v); 64 } 65 } 66 } 67 } 68 69 int agument() 70 { 71 int p=t; 72 int ans=2147483647; 73 while(p!=s) 74 { 75 ans=min(ans,e[par[p]].cap-e[par[p]].flow); 76 p=e[par[p]].u; 77 } 78 p=t; 79 while(p!=s) 80 { 81 e[par[p]].flow+=ans; 82 e[par[p]^1].flow-=ans; 83 p=e[par[p]].u; 84 } 85 return ans; 86 } 87 88 int isap() 89 { 90 memset(num,0,sizeof(num)); 91 int flow=0; 92 for(int i=1;i<=t;i++) 93 { 94 num[d[i]]++; 95 cur[i]=fir[i]; 96 } 97 int p=s; 98 while(d[s]<t) 99 { 100 if(p==t) 101 { 102 flow+=agument(); 103 p=s; 104 } 105 bool ok=0; 106 for(int i=cur[p];i;i=nxt[i]) 107 { 108 if(e[i].cap>e[i].flow && d[p]==d[e[i].v]+1) 109 { 110 ok=1; 111 par[e[i].v]=i; 112 cur[p]=i; 113 p=e[i].v; 114 break; 115 } 116 } 117 if(!ok) 118 { 119 int mn=t-1; 120 for(int i=fir[p];i;i=nxt[i]) 121 { 122 if(e[i].cap>e[i].flow)mn=min(mn,d[e[i].v]); 123 } 124 if(--num[d[p]]==0)break; 125 num[d[p]=mn+1]++; 126 cur[p]=fir[p]; 127 if(p!=s)p=e[par[p]].u; 128 } 129 } 130 return flow; 131 } 132 133 int main() 134 { 135 n=read();m=read();; 136 memset(nxt,0,sizeof(nxt)); 137 memset(fir,0,sizeof(fir)); 138 cnt=1; 139 s=1; 140 t=n*m+2; 141 for(int i=1;i<=n;i++) 142 { 143 for(int j=1;j<=m;j++) 144 { 145 wk[i][j]=read(); 146 sum+=wk[i][j]; 147 add(s,(i-1)*m+j+1,wk[i][j]*2); 148 add((i-1)*m+j+1,s,0); 149 } 150 } 151 for(int i=1;i<=n;i++) 152 { 153 for(int j=1;j<=m;j++) 154 { 155 lk[i][j]=read(); 156 sum+=lk[i][j]; 157 add((i-1)*m+j+1,t,lk[i][j]*2); 158 add(t,(i-1)*m+j+1,0); 159 } 160 } 161 for(int i=1;i<=n-1;i++) 162 { 163 for(int j=1;j<=m;j++) 164 { 165 x=read(); 166 sum+=x; 167 kkk[i][j]=x; 168 add(s,(i-1)*m+j+1,x); 169 add((i-1)*m+j+1,s,0); 170 add(s,i*m+j+1,x); 171 add(i*m+j+1,s,0); 172 } 173 } 174 for(int i=1;i<=n-1;i++) 175 { 176 for(int j=1;j<=m;j++) 177 { 178 x=read(); 179 sum+=x; 180 add((i-1)*m+j+1,t,x); 181 add(t,(i-1)*m+j+1,0); 182 add(i*m+j+1,t,x); 183 add(t,i*m+j+1,0); 184 add(1+(i-1)*m+j,1+i*m+j,kkk[i][j]+x); 185 add(1+i*m+j,1+(i-1)*m+j,kkk[i][j]+x); 186 } 187 } 188 memset(kkk,0,sizeof(kkk)); 189 for(int i=1;i<=n;i++) 190 { 191 for(int j=1;j<=m-1;j++) 192 { 193 x=read(); 194 sum+=x; 195 kkk[i][j]=x; 196 add(s,(i-1)*m+j+1,x); 197 add((i-1)*m+j+1,s,0); 198 add(s,(i-1)*m+j+2,x); 199 add((i-1)*m+j+2,s,0); 200 } 201 } 202 for(int i=1;i<=n;i++) 203 { 204 for(int j=1;j<=m-1;j++) 205 { 206 x=read(); 207 sum+=x; 208 add((i-1)*m+j+1,t,x); 209 add(t,(i-1)*m+j+1,0); 210 add((i-1)*m+j+2,t,x); 211 add(t,(i-1)*m+j+2,0); 212 add(1+(i-1)*m+j,(i-1)*m+j+2,kkk[i][j]+x); 213 add((i-1)*m+j+2,1+(i-1)*m+j,kkk[i][j]+x); 214 } 215 } 216 bfs(); 217 printf("%d\n",sum-isap()/2); 218 return 0; 219 }
原文：http://www.cnblogs.com/winmt/p/6257039.html
