O(n^4)

/*求最小值就把权值全部取相反数， 继续套这个最大值的模板*/ #include <iostream> #include<cstring> #include<cstdio> #include<cmath> const int maxn = 101; const int INF = (1<<31)-1; int w[maxn][maxn]; int lx[maxn],ly[maxn]; //顶标 int linky[maxn];//linky标记与y相连的x编号 int visx[maxn],visy[maxn];//标记顶点是否被覆盖 int slack[maxn];//用来求顶标的修改值 int nx,ny;//左右两边的顶点数目 bool find(int x)//匈牙利算法 { visx[x] = true;//x顶点被覆盖 for(int y = 0; y < ny; y++)//从x顶点出发访问与之相连的y中的所有顶点 { if(visy[y])//如果y已经被覆盖 continue; int t = lx[x] + ly[y] - w[x][y]; if(t==0)//如果x,y顶标和符合边的权重 { visy[y] = true;//覆盖y if(linky[y]==-1 || find(linky[y]))//如果y在x中没有匹配或者匹配可以被更改 { linky[y] = x; return true; //找到增广轨 } } else if(slack[y] > t) slack[y] = t;//保持slack是以y集合中顶点i为终点算出的t中最小的那个 } return false; //没有找到增广轨（说明顶点x没有对应的匹配，与完备匹配(相等子图的完备匹配)不符） } int KM() //返回最优匹配的值 { int i,j; memset(linky,-1,sizeof(linky)); memset(ly,0,sizeof(ly)); for(i = 0; i < nx; i++) for(j = 0,lx[i] = -INF; j < ny; j++) if(w[i][j] > lx[i])//lx[i]初始化为与之相连的最大权重 lx[i] = w[i][j]; for(int x = 0; x < nx; x++)//对x集合中每个顶点 { for(i = 0; i < ny; i++)//考察y集合的每个顶点 slack[i] = INF;//初始化修改最小代价为INF while(true) { memset(visx,0,sizeof(visx));//左右顶点最开始都没有被覆盖 memset(visy,0,sizeof(visy)); if(find(x)) //找到增广轨，退出 break; int d = INF; for(i = 0; i < ny; i++) //没找到，对y顶标做调整(这会增加相等子图的边)，重新找 { if(!visy[i] && d > slack[i])//y集合中顶点i没有被覆盖且slack[i]更小就减小代价d d = slack[i]; } for(i = 0; i < nx; i++) { if(visx[i]) lx[i] -= d;//x顶标减去d（总权值减少） } for(i = 0; i < ny; i++) { if(visy[i])//如果i已经被覆盖 ly[i] += d;//y顶标加上d else slack[i] -= d;//如果i没有被覆盖 } } } int result = 0; for(i = 0; i < ny; i++) if(linky[i]>-1)//如果y集合中i找到了匹配的x result += w[linky[i]][i]; return result; } int main() { scanf("%d%d",&nx,&ny); int a,b,c; while(scanf("%d%d%d",&a,&b,&c),a+b+c) { w[a][b]=c; } printf("%d\n",KM()); break; return 0; }

O(n^3)

/* O(n^3),把边权赋值为负数求的是花费最小的匹配。 */ #include <cstdio> #include <cstring> #include <cmath> #define INF 0x3f #define maxn 25 using namespace std; int nx,ny,linky[maxn]; double lack,w[maxn][maxn],lx[maxn],ly[maxn]; bool visx[maxn],visy[maxn]; bool find(int x){ visx[x]=true; for(int i=1;i<=ny;i++){ if(visy[i]) continue; int t=lx[x]+ly[i]-w[x][i]; if(t<0){ visy[i]=true; if(linky[i]==-1||find(linky[i])){ linky[i]=x; return true; } }else if(t<lack) lack=t;//注意这里的顺序 } return false; } double KM(){ memset(linky,-1,sizeof(linky)); for(int i=1;i<=ny;i++) ly[i]=0; for(int i=1;i<=nx;i++){ lx[i]=INF; for(int j=1;j<=ny;j++) if(w[i][j]>lx[i]) lx[i]=w[i][j]; } for(int x=1;x<=nx;x++){ while(true){ memset(visx,0,sizeof(visx)); memset(visy,0,sizeof(visy)); lack=INF; if(find(x)) break; for(int i=1;i<=ny;i++){ if(visx[i]) lx[i]-=lack; if(visy[i]) ly[i]+=lack; } } } int ans=0; for(int i=1;i<=ny;i++) ans-=w[linky[i]][i]; return ans; }

转载于:https://www.cnblogs.com/leotan0321/p/6081396.html