spoj 839 Optimal Marks （最小割）

这是《最小割模型在信息学竞赛中的应用》里的一道例题。

从二进制考虑，每个二进制位都用最小割来求解。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=505,M=3005,INF=0x3f3f3f3f;
const int mxN=N,mxM=M*4+2*N;
int n,m;
int lx[M],ly[M];
int v[N];
bool mk[N];
int p;
struct graph{
	int S,T;
	int base[mxN],vec[mxM],pre[mxM],tot;
	int c[mxM];
	int d[mxN],q[mxN];
	bool vis[mxN];
	void init()
	{
		memset(base,0,sizeof(base));
		tot=1;
	}
	void link(int x,int y,int z)
	{
		vec[++tot]=y; pre[tot]=base[x]; base[x]=tot; c[tot]=z;
		vec[++tot]=x; pre[tot]=base[y]; base[y]=tot; c[tot]=0;
	}
	void build()
	{
		S=0; T=n+1;
		for (int i=1;i<=m;i++) link(lx[i],ly[i],1),link(ly[i],lx[i],1);
		for (int i=1;i<=n;i++)
		{
			if (!mk[i]) continue;
			if (v[i]&1<<p) link(S,i,INF);
			else link(i,T,INF);
		}
	}
	void update(int u)
	{
		vis[u]=1;
		v[u]|=1<<p;
		for (int now=base[u];now;now=pre[now])
		{
			int v=vec[now];
			if (vis[v]||c[now]==0) continue;
			update(v);
		}
	}
	void work()
	{
		for (int i=S;i<=T;i++) vis[i]=0;
		update(S);
	}
	bool bfs()
	{
		int head=0,tail=0;
		memset(d,-1,sizeof(d));
		d[S]=0;
		q[++tail]=S;
		while(head<tail)
		{
			head++;
			int u=q[head];
			for (int now=base[u];now;now=pre[now])
			{
				int v=vec[now];
				if (d[v]==-1&&c[now]>0)
				{
					d[v]=d[u]+1;
					q[++tail]=v;
					if (v==T) return 1;
				}
			}
		}
		return 0;
	}
	int dfs(int u,int flow)
	{
		int r=0;
		if (u==T) return flow;
		for (int now=base[u];now&&r<flow;now=pre[now])
		{
			int v=vec[now];
			if (c[now]>0&&d[v]==d[u]+1)
			{
				int x=min(c[now],flow-r);
				x=dfs(v,x);
				r+=x;
				c[now]-=x;
				c[now^1]+=x;
			}
		}
		if (!r)d[u]=-2;
		return r;
	}
	int dinic()
	{
		int ans=0;
		while(bfs())
			ans+=dfs(S,INF);
		return ans;
	}
}G;
void read()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) mk[i]=0,v[i]=0;
	for (int i=1;i<=m;i++) scanf("%d%d",&lx[i],&ly[i]);
	int k; scanf("%d",&k);
	for (int i=1;i<=k;i++)
	{
		int x; scanf("%d",&x);
		mk[x]=1;
		scanf("%d",&v[x]);
	}
}
int main()
{
	int t; scanf("%d",&t);
	while(t--)
	{
		read();
		for (p=0;p<31;p++)
		{
			G.init();
			G.build();
			G.dinic();
			G.work();
		}
		for (int i=1;i<=n;i++) printf("%d\n",v[i]);
	}
}