【BZOJ2400】Optimal Marks

题意

定义无向图中的一条边的值为：这条边连接的两个点的值的异或值。

定义一个无向图的值为：这个无向图所有边的值的和。

给你一个有 \(n\) 个结点 \(m\) 条边的无向图。其中的一些点的值是给定的，而其余的点的值由你决定（但要求均为非负数），使得这个无向图的值最小。在无向图的值最小的前提下，使得无向图中所有点的值的和最小。

题解

对每一位单独考虑。对于已经确定的数，如果当前位是 \(0\) 则与起点连边，为 \(1\) 则与终点连边，然后原图上的边容量为 \(1\) 的边。这样对于未知的点我们选择是 \(0\) 还是 \(1\) ，就要把连到另一个集合的边给砍掉，我们最小化砍掉的边，即求最小割。

求第二个答案也很好求，我们直接 dfs 求出哪些点属于 \(T\) 集合即可。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

inline int gi()

{

	char c; int x=0,f=1;

	for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;

	for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';

	return x*f;

}

typedef long long ll;

const int N=505,M=20005,inf=1<<30;

int head[N],nxt[M],to[M],wei[M],lev[N],q[N],tot=1,n,m,s=1,t,u[M],v[M],w[N];

bool vis[N];

ll ans1,ans2,nw[N];

void addedge(int u, int v, int w) {

	nxt[++tot]=head[u],head[u]=tot,to[tot]=v,wei[tot]=w;

	nxt[++tot]=head[v],head[v]=tot,to[tot]=u,wei[tot]=0;

}

bool bfs()

{

	memset(lev,-1,sizeof(lev));

	int l=0,r=0;

	q[0]=s; lev[s]=1;

	while(l<=r)

	{

		int u=q[l++];

		for(int e=head[u];e;e=nxt[e])

			if(lev[to[e]]==-1&&wei[e])

			{

				lev[to[e]]=lev[u]+1;

				if(to[e]==t) return true;

				q[++r]=to[e];

			}

	}

	return false;

}

int dfs(int u, int mx)

{

	if(u==t) return mx;

	int l=mx;

	for(int e=head[u];e&&l;e=nxt[e])

		if(lev[to[e]]==lev[u]+1&&wei[e]>0)

		{

			int f=dfs(to[e],min(l,wei[e]));

			if(!f) lev[to[e]]=-1;

			l-=f,wei[e]-=f,wei[e^1]+=f;

		}

	return mx-l;

}

void vist(int u)

{

	vis[u]=true;

	for(int e=head[u];e;e=nxt[e])

		if(!vis[to[e]]&&wei[e^1]) vist(to[e]);

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("1919.in","r",stdin);

#endif

	n=gi(),m=gi();

	s=n+1,t=n+2;

	for(int i=1;i<=n;++i) w[i]=gi();

	for(int i=1;i<=m;++i) u[i]=gi(),v[i]=gi();

	for(int i=0;i<=30;++i)

	{

		memset(head,0,sizeof(head)),tot=1;

		memset(vis,false,sizeof(vis));

		for(int j=1;j<=n;++j)

			if(w[j]>=0)

			{

				if(w[j]&(1<<i)) addedge(j,t,inf);

				else addedge(s,j,inf);

			}

		for(int j=1;j<=m;++j) addedge(u[j],v[j],1),addedge(v[j],u[j],1);

		int tmp=0; while(bfs()) tmp+=dfs(s,inf);

		ans1+=1ll*tmp*(1<<i);

		vist(t);

		for(int j=1;j<=n;++j) if(vis[j]) nw[j]+=(1<<i);

	}

	printf("%lld\n",ans1);

	for(int i=1;i<=n;++i) w[i]<0?ans2+=nw[i]:ans2+=w[i];

	printf("%lld",ans2);

}