BZOJ3774 最优选择（网络流最小割二元关系）

BZOJ3774 最优选择（网络流最小割二元关系）
对于两个０１变量，如果我们把图造成这个样子：

ａ为ｘ为０的代价，ｃ为ｘ为１的代价。
ｂ，ｄ同理于ｙ
那么ｘ，ｙ之间好像没有关系。

那么如果最小花费为最小割，可以列出４个关于ａｂｃｄｅｆ的方程使得图中最小割为最小花费。
BZOJ3774 最优选择（网络流最小割二元关系）
然后我们就可以用最大流（最小割）初步处理二元关系了。
这时２ｅ＝ｖ１＋ｖ２－ｖ３－ｖ４＝－Ｋ
这里说的是如果K　＝　ｖ３　＋　ｖ４　－　ｖ１　－　ｖ２（相异减相同）小于０，那么ｅ会小于０，无法建图，这时我们将一个点对源汇的连边交换，就可以得到ｅ＝－Ｋ／２，大于等于０，可以建图。
如果二元关系构成了一个二分图，那么我们可以将一部中的所有点的对源汇的连边交换来处理Ｋ小于０的情况（比如说此题）。

那么我们来试着建模：
ｘ与ｘ１（表示四周是否被占）：
BZOJ3774 最优选择（网络流最小割二元关系）
注意中间的边是两条有向边，因为情况不能统一。
我们可以通过想来算出这个图：
我们先将答案加上所有的Ｂ的两倍，表示每个点被占和四周被占，之后再来删。
上图对于ｘ，左边是不被占，右边是被占，对于ｘ１，左边是四周被占，右边是四周不被占。（ｘ和ｘ１相异小于ｘ与ｘ１相同）
那么ｘ选左就是Ｂ，选右就是Ａ（记住我们现在是算Ｂ的两倍减去最小割，这个权值代表代价）
ｘ１也选左就是０，ｘ和ｘ１一起选右就是Ａ＋Ｂ，ｘ选右，ｘ１选左就是Ａ＋Ｂ，ｘ选左，ｘ１选右就是Ｂ＋Ｂ，完了。。。
然后ｘ１与四周就是ｘ１有，四周有１个没有，费用为ｉｎｆ，这个相异为ｉｎｆ，不用转，这虽然不是一个二分图，但是我们都把图都建出来了就算了吧。（ｘ１可以不要就是一个二分图，但这样就不好套了）

ＡＣ　Ｃｏｄｅ：

#include<bits/stdc++.h>
#define maxn 2*55*55
#define inf 0x3f3f3f3f
#define maxm maxn * 100
using namespace std;

int n,m;
int buf[maxn],info[maxn],Prev[maxm],to[maxm],cap[maxm],cnt_e=1;
inline void Node(int u,int v,int c){ Prev[++cnt_e]=info[u],info[u]=cnt_e,to[cnt_e]=v,cap[cnt_e]=c; }
inline void Line(int u,int v,int c){ Node(u,v,c),Node(v,u,0);}
int mark[55][55],a[55][55],b[55][55];
int ans = 0;
int S , T , tot;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}},dis[maxn];

int aug(int now,int Max)
{
	if(now == T) return Max;
	int inc , st = Max;
	for(int i=info[now];i && st;i=Prev[i])
		if(cap[i] && dis[to[i]] + 1 == dis[now])
		{
			inc = aug(to[i] , min(cap[i] , st));
			if(inc) st -= inc , cap[i] -= inc , cap[i^1] += inc;
			else dis[to[i]] = 0;
			if(!st) break;
		}
	return Max - st;
}

bool BFS()
{
	static queue<int>q;
	memset(dis,-1,sizeof dis);
	dis[T] = 0 , q.push(T);
	for(int now;!q.empty();)
	{
		now = q.front() , q.pop();
		for(int i=info[now];i;i=Prev[i])
			if(cap[i^1] && dis[to[i]] == -1)
			{
				dis[to[i]] = dis[now] + 1;
				q.push(to[i]);
			}
	}
	return dis[S] != -1;
}

int main()
{
	
	//freopen("1.in","r",stdin);
	scanf("%d%d",&n,&m);
	S = n * m + 1 , T = n * m + 2;
	tot = T;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			mark[i][j] = (i-1) * m + j;
			if((i+j) & 1) Line(mark[i][j],T,a[i][j]);
			else	 Line(S,mark[i][j],a[i][j]);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&b[i][j]);
			if(!((i+j) & 1)) Line(mark[i][j],T,b[i][j]);
			else Line(S,mark[i][j],b[i][j]);
			ans += b[i][j] * 2;
			
			++tot;
			if((i+j) & 1) Line(tot,T,b[i][j]) , Line(mark[i][j],tot,b[i][j]);
			else Line(S,tot,b[i][j]) , Line(tot,mark[i][j],b[i][j]);
				
			for(int d=0,x,y;d<4;d++)
				if((x=i+dir[d][0])>=1 && x<=n && (y=j+dir[d][1])>=1 && y<=m)
					if((i+j) & 1) Line(mark[x][y],tot,inf);
					else Line(tot,mark[x][y],inf);
		}
	memcpy(buf,info,sizeof info);
	for(;BFS();)
		ans -= aug(S,inf),
		memcpy(info,buf,sizeof buf);
	printf("%d\n",ans);
}

BZOJ3774 最优选择（网络流最小割二元关系）

相关推荐