[bzoj2127]happiness

• 这题学长说可以转化为最大权闭合子图，然鹅我当时没有听懂。看了题解，大家有的在列方程搞事情，我也不是很懂。有一篇博客给了一张图，我拿着图搞了搞，好像会了一种算法。（不算是自己想出来的吧，图已经给了大致思路，只能说细节是自己实现的）。
• 先来盗一下图。
• 这个图好nb，看懂这张图这题基本就做完了。我们要给每个人选一个科目，让总的价值最大。这类问题如何用网络流解呢？还是从简入手，我们先考虑只有两个人的情况，这就是这张图的由来。
• 两个人有四种情况，（$x$x选文，$y$y选理）、（$x$x选理，$y$y选文）、（两人都选文）、（两人都选理）。题目让求最大值，而我们网络流求最大流最小割，求的都是最小值。因此，我们需要转化一下。先把所有情况对答案的贡献累加，然后跑最小割去掉最小代价使方案合法。
• 我们先把$x$x选文、$x$x选理、$y$y选文、$y$y选理、$x$x和$y$y都选文、$x$x和$y$y都选理的代价累加。这时，按照图中那样建图，割掉一条边代表不使用这个状态。从$S$S到$x$x连一条边，代表$x$x选了文，其他同理。向$T$T连边代表选了理。你发现，这样建图的好处在于，你割的方案正好对应了四种情况。
• 这时候，就是合理给边赋值，跑最小割了。使$S$S到$x$x的边容量为$x$x选文的价值加上同时选文价值的一半。$y$y同理。使$x$x到$T$T的边容量为$x$x选理的价值加上同选理的价值的一半，$y$y同理。$x$x向$y$y连边的容量为同选文价值的一半加上同选理价值的一半。这样，假如你割掉了$a$a，$d$d，那么你必须割掉$e$e。代表你选择去掉$x$x选文的情况、$y$y选理的情况，答案就是初始$sum-maxflow$sum−maxflow。
• 拓展到多点也是一样，注意这题卡精度，可以先把权值乘2最后再除掉。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e4+10;
const int M=2e5+10;
const int inf=1e9;
map<pair<int,int>,int>w;
int n,m,s,t,tot=1,we[N],li[N],ver[M],Next[M],lin[N],edge[M],d[N],maxflow,flow,sum;
int cal(int i,int j){return (i-1)*m+j;}
void add(int x,int y,int z){
	ver[++tot]=y;Next[tot]=lin[x];lin[x]=tot;edge[tot]=z;
	ver[++tot]=x;Next[tot]=lin[y];lin[y]=tot;edge[tot]=0;
}
bool bfs(){
	memset(d,0,sizeof(d));
	queue<int>q;
	d[s]=1,q.push(s);
	while(q.size()){
		int x=q.front();q.pop();
		for(int i=lin[x];i;i=Next[i]){
			int y=ver[i];
			if(!d[y]&&edge[i]){
				d[y]=d[x]+1;
				q.push(y);
				if(y==t) return 1;
			}
		}
	}
	return 0;
}
int dinic(int x,int flow){
	if(x==t) return flow;
	int rest=flow;
	for(int i=lin[x];i&&rest;i=Next[i]){
		int y=ver[i];
		if(d[y]==d[x]+1&&edge[i]){
			int k=dinic(y,min(edge[i],rest));
			if(!k) d[y]=0;
			rest-=k;edge[i]-=k;edge[i^1]+=k;
			if(!rest) return flow-rest;
		}
	}
	return flow-rest;
}
int main(){
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&we[cal(i,j)]),sum+=we[cal(i,j)],we[cal(i,j)]*=2;
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&li[cal(i,j)]),sum+=li[cal(i,j)],li[cal(i,j)]*=2;
	for(int i=2;i<=n;++i) for(int j=1;j<=m;++j){
		int c;scanf("%d",&c);sum+=c;
		c*=2;
		we[cal(i,j)]+=c/2;we[cal(i-1,j)]+=c/2;
		w[make_pair(cal(i,j),cal(i-1,j))]=c/2;
	}
	for(int i=2;i<=n;++i) for(int j=1;j<=m;++j){
		int c;scanf("%d",&c);sum+=c;
		c*=2;
		li[cal(i,j)]+=c/2;li[cal(i-1,j)]+=c/2;
		c/=2;
		c+=w[make_pair(cal(i,j),cal(i-1,j))];
		add(cal(i,j),cal(i-1,j),c);add(cal(i-1,j),cal(i,j),c);
	}
	for(int i=1;i<=n;++i) for(int j=2;j<=m;++j){
		int c;scanf("%d",&c);sum+=c;
		c*=2;
		we[cal(i,j)]+=c/2;we[cal(i,j-1)]+=c/2;
		w[make_pair(cal(i,j),cal(i,j-1))]=c/2;
	}
	for(int i=1;i<=n;++i) for(int j=2;j<=m;++j){
		int c;scanf("%d",&c);sum+=c;
		c*=2;
		li[cal(i,j)]+=c/2;li[cal(i,j-1)]+=c/2;
		c/=2;
		c+=w[make_pair(cal(i,j),cal(i,j-1))];
		add(cal(i,j),cal(i,j-1),c);add(cal(i,j-1),cal(i,j),c);
	}
	s=0,t=n*m+1;
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){
		add(s,cal(i,j),we[cal(i,j)]);
		add(cal(i,j),t,li[cal(i,j)]);
	}
	while(bfs()){
		while(flow=dinic(s,inf)) maxflow+=flow;
	}
	printf("%d\n",sum-maxflow/2);
	return 0;
}