bzoj1976【Beijing2010组队】能量魔方Cube

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最小割，思路很好。

我们可以发现这道题与之前的几道题略有不同，这里是两个格子所属类别不同时获得某种收益。所以我们单纯地按照两个类别建立源点和汇点，连边求最小割就行不通了。

那怎么办呢？能不能还用最小割解决呢？

答案当然是能，不然我第一行为什么会写“最小割”三个字…2333

我们考虑能不能有一种方案，让任意两个相邻格子颜色都不同。当然是可以的，只要对一个n*n*n的立方体黑白染色就可以了。对于黑色，我们用s表示positive，t表示negative；相反地，对于白色，用s表示negative，t表示positive。这样，我们就把所属与不同类别转化为所属相同类别。是不是很机智啊！

但是题目中是有限定条件的，也就是有些点的类别是固定的，这也很好办。比如说对于黑色，如果已经确定为positive，连边(s,i,inf)；如果已经确定为negative，连边(i,t,inf)。因为inf的边一定不会成为割，也就保证了i节点一定属于s割或者t割，即保证了它是positive或者negative。白色同理。

然后对于任意两个相邻格子i和j，连边（i,j,1）（j,i,1）。

最后跑一次最小割，从总收益中减去最小割即为答案。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define pa pair<int,int>
#define maxn 70000
#define maxm 700000
#define inf 1000000000
#define f(x,y,z) ((x-1)*n*n+(y-1)*n+z)
using namespace std;
struct edge_type
{
	int next,to,v;
}e[maxm];
int head[maxn],cur[maxn],dis[maxn];
int n,m,s,t,ans=0,cnt=1;
char ch;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void add_edge(int x,int y,int v1,int v2)
{
	e[++cnt]=(edge_type){head[x],y,v1};head[x]=cnt;
	e[++cnt]=(edge_type){head[y],x,v2};head[y]=cnt;
}
inline bool bfs()
{
	queue<int>q;
	memset(dis,-1,sizeof(dis));
	dis[s]=0;q.push(s);
	while (!q.empty())
	{
		int tmp=q.front();q.pop();
		if (tmp==t) return true;
		for(int i=head[tmp];i;i=e[i].next) if (e[i].v&&dis[e[i].to]==-1)
		{
			dis[e[i].to]=dis[tmp]+1;
			q.push(e[i].to);
		}
	}
	return false;
}
inline int dfs(int x,int f)
{
	int tmp,sum=0;
	if (x==t) return f;
	for(int &i=cur[x];i;i=e[i].next)
	{
		int y=e[i].to;
		if (e[i].v&&dis[y]==dis[x]+1)
		{
			tmp=dfs(y,min(f-sum,e[i].v));
			e[i].v-=tmp;e[i^1].v+=tmp;sum+=tmp;
			if (sum==f) return sum;
		}
	}
	if (!sum) dis[x]=-1;
	return sum;
}
inline void dinic()
{
	while (bfs())
	{
		F(i,1,t) cur[i]=head[i];
		ans+=dfs(s,inf);
	}
}
int main()
{
	n=read();
	s=n*n*n+1;t=s+1;
	F(i,1,n) F(j,1,n) F(k,1,n)
	{
		if (i!=n) add_edge(f(i,j,k),f(i+1,j,k),1,1);
		if (j!=n) add_edge(f(i,j,k),f(i,j+1,k),1,1);
		if (k!=n) add_edge(f(i,j,k),f(i,j,k+1),1,1);
	}
	F(i,1,n) F(j,1,n) F(k,1,n)
	{
		ch=getchar();while (ch!='P'&&ch!='N'&&ch!='?') ch=getchar();
		if (ch=='P')
		{
			if ((i+j+k)%2) add_edge(s,f(i,j,k),inf,0);
			else add_edge(f(i,j,k),t,inf,0);
		}
		else if (ch=='N')
		{
			if ((i+j+k)%2) add_edge(f(i,j,k),t,inf,0);
			else add_edge(s,f(i,j,k),inf,0);
		}
	}
	dinic();
	printf("%d\n",3*n*n*(n-1)-ans);
}

bzoj1976【Beijing2010组队】能量魔方Cube

原文：http://blog.csdn.net/aarongzk/article/details/50375976