正题

首先我们要了解几个概念。
顶标 $t{x}_i,t{y}_i$ 分别表示的是人为赋予的左右点的点权，在运算过程中，需要满足$$t{x}_u+t{y}_v\ge w_{u,v}$$
相等子图：每一个点与满足 $t{x}_u+t{y}_v=w_{u,v}$ 的边构成的子图。
定理：若相等子图存在完美匹配，则这个完美匹配的权值就是最大的。
证明：首先对于任意一个完美匹配的值满足：$$\sum _{e\in A}{w}_e\le \sum _{i=1}^{n}t{x}_i+t{y}_i$$
其次，若相等子图存在完美匹配，则该匹配满足：$$\sum _{e\in A}{w}_e=\sum _{i=1}^{n}t{x}_i+t{y}_i$$
我们先来讨论一下较为简单的算法流程。

首先将左边点的顶标 $t{x}_i$ 设置为 $i$ 出边中的权值最大值， $t{y}_i$ 设为 $0$ 。

接着依次枚举各个点 $i$ ，再枚举这个点的出边，如果出边对应的点 $j$ 满足：$$t{x}_i+t{y}_j=w_{i,j}$$
就讨论：

1.若$j$点没有匹配的点，那么连边 $return$ 就可以了。

2.否则就$dfs$ j的匹配点，完成上述步骤。

如果最后能找到一条增广路，那么说明当前的顶标就是可行的。

否则我们要尝试另外一种顶标方案使其可以找到增广路。

我们用两个bool数组 $vx,vy$ 分别记录左右两边点是否被遍历过。

由于增广不成功，增广路上面的肯定是一些左右点的可行匹配。

设 $d$ 是满足左边的点被遍历了，右边的点没有被遍历的边中 $t{x}_i+t{y}_j-w_{i,j}$ 最小的。

考虑将遍历过的左边点的 $t{x}_i=t{x}_i-d$ ，右边点的 $t{y}_j=t{y}_j+d$ 。

对于一条边来说：

1.若左右两边点都被遍历过， $t{x}_i+t{y}_j-w_{i,j}$ 不会变，是否匹配的状态也不会变。

2.若左右两边点都没有被遍历过，同上。

3.若左边的点被遍历了，右边的点没有， $t{x}_i+t{y}_j-w_{i,j}$ 变小，这条边可能会被加入相等子图中。

4.若左边的点没有被遍历，有边的点有，$t{x}_i+t{y}_j-w_{i,j}$ 变大，这条边不可能被加入相等子图中。

实际上我们更关注的是第三点，因为一条失败的增广路都是走到左边点停了。

但因为我们想要使得相等子图存在增广路的同时，顶标和尽可能大，所以自然就想让 $d$ 小一些。

上述做法时间复杂度瓶颈在于每次都需要重新找增广路，每次时间复杂度 $O(n+m)$ 。

总时间复杂度就变成了 $O(n^2(n+m))$ 。

实际上有更好的方法。
考虑 $bfs$ ，用一个 $slack$ 数组表示一个右边点所连边中 $t{x}_i+t{y}_j-w_{i,j}$ 最小值。

这样我们只需要将可能增广的左节点不断加入队列，考虑当前左端点所连右端点，更新其slack值。

若满足该点 $slack=0$ ，就可以观察这个右端点是否有匹配点，如果没有，那么就找到了合法增广路，如果有，就将那个匹配点加入队列。

每次我们寻找不在增广路上的 $slack$ 最小值即可作为 $d$ 值，更新就可以了，在此过程中，不用每次都重新构建，时间复杂度大大减小，总共有 $n$ 个点进行增广，只会更改 $n$ 次顶标，每次更改时间复杂度 $O(n)$ ，时间复杂度 $O(n^3)$ 。

#include<bits/stdc++.h>
using namespace std;

const int N=510;
bool vx[N],vy[N];
long long tx[N],ty[N],slc[N],w[N][N];
int mx[N],my[N],pre[N],n,m;
int qs[N],st,ed;

bool check(int y){
	vy[y]=true;
	if(my[y]){
		vx[my[y]]=true;
		qs[++ed]=my[y];
		return false;
	}
	while(y){
		my[y]=pre[y];
		swap(mx[my[y]],y);
	}
	return true;
}

void find(int x){
	qs[st=ed=1]=x;vx[x]=true;
	while(1){
		while(st<=ed){
			int x=qs[st++];
			for(int y=1;y<=n;y++) if(w[x][y]!=-20000000 && !vy[y]){
				long long d=tx[x]+ty[y]-w[x][y];
				if(d<slc[y]){
					pre[y]=x;
					if(d) slc[y]=d;
					else if(check(y)) return ;
				}
			}
		}
		long long mmin=slc[0];
		for(int i=1;i<=n;i++) if(!vy[i]) mmin=min(mmin,slc[i]);
		for(int i=1;i<=n;i++){
			if(vx[i]) tx[i]-=mmin;
			if(vy[i]) ty[i]+=mmin;
			else slc[i]-=mmin;
		}
		for(int i=1;i<=n;i++)
			if(!vy[i] && !slc[i] && check(i)) return ;
	}
}

void solve(){
	for(int i=1;i<=n;i++) tx[i]=-20000000;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
		tx[i]=max(tx[i],w[i][j]);
	for(int i=1;i<=n;i++){
		memset(vx,false,sizeof(vx));
		memset(vy,false,sizeof(vy));
		memset(slc,63,sizeof(slc));
		find(i);
		
	}
	long long ans=0;
	for(int i=1;i<=n;i++) ans+=tx[i]+ty[i];
	printf("%lldn",ans);
	for(int i=1;i<=n;i++) printf("%d ",my[i]);
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) w[i][j]=-20000000;
	int x,y,c;
	for(int i=1;i<=m;i++) scanf("%d %d %d",&x,&y,&c),w[x][y]=c;
	solve();
}

最后

以上就是霸气招牌为你收集整理的二分图最佳完美匹配正题的全部内容，希望文章能够帮你解决二分图最佳完美匹配正题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。