https://blog.csdn.net/sixdaycoder/article/details/47720471
https://www.luogu.com.cn/blog/SingerCoder/solution-p6577
这两个都有讲错的地方,但是大概意思还是能弄懂的
bfs匈牙利+顶标限制
就是不断利用修改顶标,来扩展相等子图的规模
使得能在相等子图中完成增广。
一旦相等子图是完备子图了,就得到了最终答案。
流程是:
1.初始化建边,邻接矩阵。没有的边设置为-inf(题目为求最大权完美匹配)
2.对于左部点每一个点,依次努力配对
3.如果在子图中配对成功,则完成配对,直接返回2.
4.否则,修改顶标,返回3.
5.输出答案
利用bfs匈牙利算法+记忆增广路径可以做到O(n^3)
代码:
Luogu6577
#include<bits/stdc++.h> #define reg int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define pb push_back #define solid const auto & #define enter cout<<endl #define pii pair<int,int> using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);} template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');} namespace Modulo{ const int mod=998244353; il int ad(int x,int y){return x+y>=mod?x+y-mod:x+y;} il int sub(int x,int y){return ad(x,mod-y);} il int mul(int x,int y){return (ll)x*y%mod;} il void inc(int &x,int y){x=ad(x,y);} il void inc2(int &x,int y){x=mul(x,y);} il int qm(int x,int y=mod-2){int ret=1;while(y){if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;} template<class ...Args>il int ad(const int a,const int b,const Args &...args) {return ad(ad(a,b),args...);} template<class ...Args>il int mul(const int a,const int b,const Args &...args) {return mul(mul(a,b),args...);} } //using namespace Modulo; namespace Miracle{ const int MAXN=510; const ll inf=0x3f3f3f3f3f3f3f3f; int n,m; ll e[MAXN][MAXN]; ll lx[MAXN],ly[MAXN],slack[MAXN]; int px[MAXN],py[MAXN],pre[MAXN]; bool vx[MAXN],vy[MAXN]; queue<int> q; void aug(int v) { int t; while(v) { t=px[pre[v]]; px[pre[v]]=v; py[v]=pre[v]; v=t; } } void bfs(int s) { memset(vx,0,sizeof(vx)); memset(vy,0,sizeof(vy)); fill(slack+1,slack+n+1,inf); while(!q.empty())q.pop(); q.push(s); while(1) { while(!q.empty()) { int u=q.front();q.pop(); vx[u]=1; for(int i=1;i<=n;++i)if(!vy[i]) { if(lx[u]+ly[i]-e[u][i]<slack[i]) { slack[i]=lx[u]+ly[i]-e[u][i]; pre[i]=u; if(slack[i]==0) { vy[i]=1; if(!py[i]){aug(i);return;} else q.push(py[i]); } } } } ll d=inf; for(int i=1;i<=n;++i)if(!vy[i])d=min(d,slack[i]); for(int i=1;i<=n;++i) { if(vx[i])lx[i]-=d; if(vy[i])ly[i]+=d;else slack[i]-=d; } for(int i=1;i<=n;++i)if(!vy[i]) { if(slack[i]==0) { vy[i]=1; if(!py[i]){aug(i);return;} else q.push(py[i]); } } } } signed main() { cin>>n>>m; memset(e,0xcf,sizeof e); int x,y,z; for(int i=1;i<=m;++i){ rd(x);rd(y);rd(z); e[x][y]=z; } for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ lx[i]=max(lx[i],e[i][j]); } } for(int i=1;i<=n;++i)bfs(i); ll ans=0; for(int i=1;i<=n;++i){ ans+=e[py[i]][i]; } cout<<ans<<endl; for(int i=1;i<=n;++i){ printf("%d ",py[i]); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* */
扩展:
1.判断是否可能没有完美匹配?
跑KM,如果选了-inf边(不存在的边)就无解(和网络流判无解类似)
2.保证最大权即可,不是最大匹配也行?
不存在的边设边权为0,跑KM
3.最大权匹配(可能没有完美匹配)
右部点额外建n个虚点,每个左部点依次对应虚点连-inf边
跑KM,再减去连接的-inf边,得到真正的答案。
4.求最小权
边权取负即可