背景
唱歌的蝉 嘿 把星星都吵醒 月光晒了很凉快
就是这样回忆起来 第一次告白
尴尬的我 看 爱装得很哲学的你其实很可爱
你说活在明天 活在期待 不如活得今天很自在
我说我懂了 会不会太快 未来 第一天要展开
描述
输入格式
输出格式
样例输入
2 3 1 1 15 1 2 20 1 3 17 2 1 22 2 2 14 2 3 14
样例输出
1 2 2 1 YES
数据范围与约定
样例解释
来源
km算法
就是二分图匹配时维护lx[i],ly[i]
满足
1.对于任意边lx[i]+ly[i]>=w[i,j]
2.如果存在一组匹配,其中任意边满足lx[i]+ly[i]=w[i,j],它一定是最大匹配(如果随意调换一边,必然出现lx[i]+ly[j]+lx[i']+ly[j']=w[i,j]+w[i',j']≥w[i,j']+w[i',j]
于是每次找出slock,表示对所有找过的i,不为0的min(lx[i]+ly[j]-w[i,j])
把slock的值从左移至右,既不改变原图能走的边,又能使图得到扩充。
//一开始应该把lx[i]设成max(w[i,j],0),ly[i]设成0
每次扩充必须保证图中的边满足lx[i]+ly[i]=w[i,j],否则用slock扩充
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<functional> using namespace std; #define INF (100000000) #define MAXN (520+10) #define MAXWi (201314) int n,m,yi,slack; int w[MAXN][MAXN],lx[MAXN],ly[MAXN],a[MAXN];//a=?->yi bool vx[MAXN],vy[MAXN]; bool find(int x) { vx[x]=1; for (int i=1;i<=m;i++) if (!vy[i]) { int t=lx[x]+ly[i]-w[x][i]; if (t==0) { vy[i]=1; if (a[i]==0||find(a[i])) {a[i]=x;return 1;} }else slack=min(slack,t); } return 0; } int main() { // freopen("input","r",stdin); scanf("%d%d",&n,&yi);m=n+1; memset(lx,0,sizeof(lx)); memset(ly,0,sizeof(ly)); memset(a,0,sizeof(a)); for (int i=1;i<=n*(n+1);i++) { int u,v,wei;scanf("%d%d%d",&u,&v,&wei);w[u][v]=wei; lx[u]=max(lx[u],wei); } for (int i=1;i<=n;i++) { memset(vx,0,sizeof vx); memset(vy,0,sizeof vy); slack=INF; while (!find(i)) { for (int j=1;j<=n;j++) if (vx[j]) lx[j]-=slack; for (int j=1;j<=m;j++) if (vy[j]) ly[j]+=slack; memset(vx,0,sizeof vx); memset(vy,0,sizeof vy); slack=INF; // find(i); } } for (int i=1;i<=m;i++) { if (a[i]) printf("%d %dn",a[i],i); } if (a[yi]) printf("NOn"); else printf("YESn"); return 0; }