首页 > 代码库 > ural 1076 KM求最小权匹配
ural 1076 KM求最小权匹配
贴模板~
KM算法引进了顶标函数,不断缩小这个顶标来让相等子图的可能范围扩大
#include<iostream> #include<cstring> //KM 复杂度O^3 using namespace std; const int N=200; int lx[N],ly[N];//顶标函数 int w[N][N];//图 bool vix[N],viy[N]; int linky[N];// int lack;//每次顶标函数扩大的增量 int n,m; bool find(int x){ vix[x]=1; for(int y=1;y<=m;y++){ if(viy[y])continue; int t=lx[x]+ly[y]-w[x][y]; if(t==0){ viy[y]=1; if(linky[y]==0||find(linky[y])){ linky[y]=x; return true; } }else lack=min(lack,t); } return false; } int KM(){ memset(linky,0,sizeof(linky)); memset(lx,0,sizeof(lx)); memset(ly,0,sizeof(ly)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ lx[i]=max(lx[i],w[i][j]);//顶标函数一般初始化为lx取从i出发的边的最大值,ly为0 } } for(int x=1;x<=n;x++){ while(true){ memset(vix,0,sizeof(vix)); memset(viy,0,sizeof(viy)); lack=INF; if(find(x))break; for(int i=1;i<=n;i++){ if(vix[i])lx-=lack; } for(int i=1;i<=m;i++){ if(viy[i])ly[i]+=lack; } } } int ret=0; for(int y=1;y<=m;y++){ if(linky[y]>0)ret+=w[linky[y]][y]; } return ret; }
ural 1076 练练手
//ural 1076 #include<iostream> #include<iomanip> #include<cstring> #include<stdio.h> #include<map> #include<cmath> #include<algorithm> #include<vector> #include<stack> #include<fstream> #include<queue> #define rep(i,n) for(int i=0;i<n;i++) #define fab(i,a,b) for(int i=(a);i<=(b);i++) #define fba(i,b,a) for(int i=(b);i>=(a);i--) #define MP make_pair #define PB push_back #define cls(x) memset(x,0,sizeof(x)) #define lowbit(x) x&-x #define INF 0x7ffffff #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; const int N=160; int n,lack; int l[N],r[N],adj[N][N],match[N]; bool vix[N],viy[N]; void init(){ cls(vix); cls(viy); cls(adj); cls(l); cls(r); memset(match,-1,sizeof(match)); } bool find(int x){ vix[x]=1; fab(y,1,n){ if(viy[y])continue; int t=l[x]+r[y]-adj[x][y]; if(t==0){ viy[y]=1; if(match[y]==-1||find(match[y])){ match[y]=x; return true; } }else lack=min(lack,t); } return false; } int KM(){ fab(i,1,n){ l[i]=-INF; fab(j,1,n){ l[i]=max(l[i],adj[i][j]); } } fab(i,1,n){ while(true){ cls(vix); cls(viy); lack=INF; if(find(i))break; fab(i,1,n){ if(vix[i])l[i]-=lack; } fab(i,1,n){ if(viy[i])r[i]+=lack; } } } int ret=0; fab(i,1,n){ if(match[i]!=-1)ret+=adj[match[i]][i]; } return ret; } int main(){ ios::sync_with_stdio(false); init(); scanf("%d",&n); fab(i,1,n){ int sum=0; fab(j,1,n){ scanf("%d",&adj[i][j]); sum+=adj[i][j]; } fab(j,1,n){ adj[i][j]=sum-adj[i][j]; } } fab(i,1,n)fab(j,1,n)adj[i][j]=-adj[i][j]; printf("%d\n",-KM()); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。