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

代码中有些注释,还请学了n^4的dfs再来学习这个

#include 
   
    using namespace std;#define int long longconst int inf=1e18;const int maxn=509;int n,m,cost[maxn][maxn],mat[maxn],pre[maxn];int wisha[maxn],wishb[maxn],va[maxn],vb[maxn],slack[maxn];void init(int a[],int b){	for(int i=0;i<=n;i++)	a[i]=b;}void bfs(int u){	init( pre,0 );	init( slack,inf ); slack[0]=0;	int x=0,y=0,yy=0,delta=0;	mat[y]=u;//最开始0匹配u,为什么这么写,无关紧要,总要让一个开头嘛 	while( 1 )	{		x=mat[y], delta=inf, vb[y]=1;//现在是帮x找完美匹配 		for(int i=1;i<=n;i++)		{			if( vb[i] )	continue;//本次访问过,不用管了 			if( slack[i]>wisha[x]+wishb[i]-cost[x][i] )			{				slack[i]=wisha[x]+wishb[i]-cost[x][i];//更新最小误差期望 				pre[i]=y;			}			if( slack[i]
    
     > n >> m;	for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)			cost[i][j]=-inf;	for(int i=1;i<=m;i++)	{		int l,r,w;		cin >> l >> r >> w;		cost[l][r]=max( cost[l][r],w );	}	cout << km() << '\n';	for(int i=1;i<=n;i++)		cout << mat[i] << " ";}
    
   

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