本文共 1888 字，大约阅读时间需要 6 分钟。

胡伯涛的论文里的例题。

给定一个无向图,有些点有编号,没有编号的点需要你指定

最后这张图的权值是$\sum _{(u,v)\in E}mar{k}_u\oplus mar{k}_v$

最小化这个权值,输出你构造的编号

思路非常巧妙

因为异或运算非常难顶,但是异或的话,每一位二进制是独立的

所以可以把二进制拆分,现在只考虑最小化第$i$位的二进制贡献

问题变成了每个点是0或者1,有些点指定了,有些点需要你来加

那么如果一条边的两个点数字相同不需要计算贡献,不相同计算贡献

想到了什么??最小割!!

把$S$点集看作数字$1$,$T$点集看作数字$0$

那么$S$向已编号的数字为$1$的点连流量为$inf$得边

已编号的数字为$0$的点向$T$连流量$inf$的边

对于原图的边$(u,v)$,彼此间连流量$1$的边即可

这样就分成了两个点集

#include 
   
    using namespace std;#define int long longconst int maxn=2e5+10; const int inf=1e12;struct edge{
   	int to,nxt,flow;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,int flow){
   	d[++cnt] = (edge){
   v,head[u],flow},head[u]=cnt;	d[++cnt] = (edge){
   u,head[v],0},head[v]=cnt;}int id[maxn],p[maxn],l[maxn],r[maxn],ans[maxn];int n,m,k,s,t,dis[maxn];bool bfs(){
   	queue
    
     q;	for(int i=0;i<=t;i++)	dis[i]=0;	q.push(s); dis[s]=1;	while( !q.empty() )	{
   		int u=q.front(); q.pop();		for(int i=head[u];i;i=d[i].nxt )		{
   			int v=d[i].to;			if( d[i].flow&&dis[v]==0 )			{
   				dis[v]=dis[u]+1;				q.push(v);			}		}	}	return dis[t]!=0;}int dinic(int u,int flow){
   	if( u==t )	return flow;	int res=flow;	for(int i=head[u];i&&res;i=d[i].nxt )	{
   		int v=d[i].to;		if( dis[v]==dis[u]+1&&d[i].flow )		{
   			int temp = dinic(v,min(d[i].flow,res ));			res-=temp;			d[i].flow-=temp,d[i^1].flow+=temp;			if( temp==0 )	dis[v]=0;			} 	}	return flow-res;}signed  main(){
   	int T; cin >> T;	while( T-- )	{
   		cin >> n >> m;		for(int i=1;i<=m;i++)	scanf("%lld%lld",&l[i],&r[i]);		int k; cin >> k;		for(int i=1;i<=k;i++)			scanf("%lld%lld",&id[i],&p[i]);		for(int i=0;i<=30;i++)//枚举每一位二进制 		{
   			s=0,t=n+1,cnt=1;			for(int j=0;j<=t;j++)	head[j]=0;			for(int j=1;j<=m;j++)			{
   				add(l[j],r[j],1);				add(r[j],l[j],1);			}			for(int j=1;j<=k;j++)				if( p[j]&(1<
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109367828 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！