bzoj-2127 happiness

题意：

给出一个nxm的座位表，每个同学学文或学理有一个喜悦度；

并且如果两个挨着的同学一起学文或学理，会再有一个喜悦度加成；

喜悦度都为非负整数，n,m<=100，答案在int内；

题解：
文理分科，似乎是网络流的经典问题呢；

因为让所有人都幸福的世界是不可能存在的，所以我们就采用最小割的思想；

先将所有的喜悦度都加起来，然后将割掉一些使其合法，当然要满足割最小；

这里的建图还是去膜了黄学长，然后得到建图如下；

对于原图中所有相邻的两个人A，B，我们建边：

s->A:cost[A文]+c[文][A][B]/2,s->B:cost[B文]+c[文][A][B]/2;

A->t:cost[A理]+c[理][A][B]/2,B->t:costB[理]+c[理][A][B]/2;

A<–>B:c[文][A][B]/2+c[理][A][B]/2

建图之后，显然这个网络只有这四种割是可能最小的；

而这又恰好代表了四种不同的方案，引申到更多点也是同理的；

所以得到原图的最小割之后，用总的喜悦度减去就可以了；

为了避免精度误差将所有喜悦度翻倍之后再计算；

注意那个双向边要建真正的双向而不是两条单向，因为两条单向的复杂度会变得很奇怪。。。

代码：

#include<queue>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 110
#define M 1210000
using namespace std;
int c[6][N][N],num[N][N];
int next[M],to[M],flow[M],head[N*N],ce=1;
int S,T,dis[N*N];
queue<int>q;
void add(int x,int y,int fl)
{
	if(!x||!y)	return ;
	to[++ce]=y;
	flow[ce]=fl;
	next[ce]=head[x];
	head[x]=ce;
	to[++ce]=x;
	flow[ce]=0;
	next[ce]=head[y];
	head[y]=ce;
}
void add2(int x,int y,int fl)
{
	if(!x||!y)	return ;
	to[++ce]=y;
	flow[ce]=fl;
	next[ce]=head[x];
	head[x]=ce;
	to[++ce]=x;
	flow[ce]=fl;
	next[ce]=head[y];
	head[y]=ce;
}
bool BFS()
{
	memset(dis,0,sizeof(dis));
	dis[S]=1;
	q.push(S);
	int i,x;
	while(!q.empty())
	{
		x=q.front(),q.pop();
		for(i=head[x];i;i=next[i])
		{
			if(flow[i]&&!dis[to[i]])
			{
				dis[to[i]]=dis[x]+1;
				q.push(to[i]);
			}
		}
	}
	return dis[T]!=0;
}
int dfs(int x,int fl)
{
	if(x==T)	return fl;
	int i,ret,temp;
	for(i=head[x],ret=0;i;i=next[i])
	{
		if(flow[i]&&dis[to[i]]==dis[x]+1)
		{
			temp=dfs(to[i],min(fl-ret,flow[i]));
			ret+=temp;
			flow[i]-=temp,flow[i^1]+=temp;
			if(ret==fl)
				return ret;
		}
	}
	return ret;
}
int main()
{
	int n,m,i,j,k,x,y,ans,sum;
	scanf("%d%d",&n,&m);
	sum=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%d",&c[0][i][j]),sum+=c[0][i][j];
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%d",&c[1][i][j]),sum+=c[1][i][j];
	for(i=1;i<n;i++)
		for(j=1;j<=m;j++)
			scanf("%d",&c[2][i][j]),sum+=c[2][i][j];
	for(i=1;i<n;i++)
		for(j=1;j<=m;j++)
			scanf("%d",&c[3][i][j]),sum+=c[3][i][j];
	for(i=1;i<=n;i++)
		for(j=1;j<m;j++)
			scanf("%d",&c[4][i][j]),sum+=c[4][i][j];
	for(i=1;i<=n;i++)
		for(j=1;j<m;j++)
			scanf("%d",&c[5][i][j]),sum+=c[5][i][j];
	for(i=1,k=0;i<=n;i++)
		for(j=1;j<=m;j++)
			num[i][j]=++k;
	S=++k,T=++k,sum<<=1;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			x=num[i][j];
			add(S,x,(c[0][i][j]<<1)+c[2][i-1][j]+c[2][i][j]+c[4][i][j-1]+c[4][i][j]);
			add(x,T,(c[1][i][j]<<1)+c[3][i-1][j]+c[3][i][j]+c[5][i][j-1]+c[5][i][j]);
			add2(x,num[i+1][j],c[2][i][j]+c[3][i][j]);
			add2(x,num[i][j+1],c[4][i][j]+c[5][i][j]);
		}
	}
	ans=0;
	while(BFS())
		ans+=dfs(S,0x3f3f3f3f);
	sum-=ans;
	sum>>=1;
	printf("%d\n",sum);
	return 0;
}

bzoj-2127 happiness

原文：http://blog.csdn.net/ww140142/article/details/49100065