cogs 1873 happiness
题解：
每个人选文选理各有收益，如果没有附加权值，我们可以用最大权闭合子图的方式构建出来这个图。
用总权值之和减去最小割即是答案。
当有了附加权值，我们也假定现拥有权值，再抛去权值。
对于点对(i,j)，当i,j割边相同的话才能获得附加权值，也就是说如果ai,aj有一方被割断,附加权值a[i][j]应该提前被割断。也就是说a[i][j]要先断，才能断ai,aj，同理，b[i][j]要先断才能断bi,bj。所以这个图是长这样的：
这样就可以在ai,aj断之前先断a[i][j]。然后用ai,bi,a[i][j],b[i][j]的总和减去最小割就是最终的答案。
双倍经验cogs 1842 圈地计划。
圈地计划的附加权值是当两者选取不同时才能获得，注意到是一个网格图，所以把网格图黑白染色，让黑点翻转源汇即交换a[i],b[i]，这样就同上一道题一样了，只不过a[i][j]=b[i][j]而已。注意：虽然a[i][j]=b[i][j],但是这个附加点还是不能删的，因为a[i][j]的流量不一定都跑到b[i][j]。
code
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define fcl fclose(stdin); fclose(stdout); return 0
void Read(int& x){
char ch; while(ch=getchar(),ch<'0'||ch>'9');
x=ch-'0'; while(ch=getchar(),ch>='0'&&ch<='9') x=x*10+ch-'0';
}
int n,m,S,T;
const int INF=0x7f7f7f7f;
int W[2][110][110],L[2][110][110],R[2][110][110];
struct EDGE{
int to,next,flow;
}edge[300000];
int head[50010],tot=1;
#define ty (edge[x].to)
inline void AddEdge(int a,int b,int c){
edge[++tot].to=b;
edge[tot].flow=c;
edge[tot].next=head[a];
head[a]=tot;
}
inline void Add(int a,int b,int c){
AddEdge(a,b,c); AddEdge(b,a,0);
}
int cur[50010],dis[50010],Q[50010];
bool Bfs(){
memset(dis,0x7f,(T+1)<<2);
dis[S]=0;
int s=1,t=0,u; Q[++t]=S;
while(s<=t){
u=Q[s++];
for(int x=head[u];x;x=edge[x].next)
if(edge[x].flow&&dis[ty]==INF)
dis[ty]=dis[u]+1,Q[++t]=ty;
}
return dis[T]!=INF;
}
int Dfs(int u,int a){
if(u==T||a==0) return a;
int f2=0,f;
for(int& x=cur[u];x;x=edge[x].next){
if(edge[x].flow&&dis[ty]==dis[u]+1){
f=Dfs(ty,min(a,edge[x].flow));
edge[x].flow-=f; edge[x^1].flow+=f;
f2+=f; a-=f;
if(a==0) break;
}
}
return f2;
}
int MaxFlow(){
int res=0;
while(Bfs()){
memcpy(cur,head,(T+1)<<2);
res+=Dfs(S,INF);
}
return res;
}
int main(){
freopen("nt2011_happiness.in","r",stdin);
freopen("nt2011_happiness.out","w",stdout);
Read(n); Read(m);
int i,j,k,p,ans=0;
S=5*n*m+1,T=S+1;
for(k=0;k<2;++k)
for(i=1;i<=n;++i)
for(j=1;j<=m;++j){
Read(W[k][i][j]),ans+=W[k][i][j];
if(k==0) Add(S,(i-1)*m+j,W[k][i][j]);
else Add((i-1)*m+j,T,W[k][i][j]);
}
for(k=0;k<2;++k)
for(i=1;i<n;++i)
for(j=1;j<=m;++j){
Read(L[k][i][j]),ans+=L[k][i][j];
if(k==0){
p=n*m+(i-1)*m+j;
Add(S,p,L[k][i][j]);
Add(p,(i-1)*m+j,INF);
Add(p,i*m+j,INF);
}
else{
p=2*n*m+(i-1)*m+j;
Add(p,T,L[k][i][j]);
Add((i-1)*m+j,p,INF);
Add(i*m+j,p,INF);
}
}
for(k=0;k<2;++k)
for(i=1;i<=n;++i)
for(j=1;j<m;++j){
Read(R[k][i][j]),ans+=R[k][i][j];
if(k==0){
p=3*n*m+(i-1)*m+j;
Add(S,p,R[k][i][j]);
Add(p,(i-1)*m+j,INF);
Add(p,(i-1)*m+j+1,INF);
}
else{
p=4*n*m+(i-1)*m+j;
Add(p,T,R[k][i][j]);
Add((i-1)*m+j,p,INF);
Add((i-1)*m+j+1,p,INF);
}
}
ans-=MaxFlow();
printf("%d
",ans);
fcl;
}