给定一个n*n矩阵，每个格子里都有一个正整数w(i,j)。你的任务是给每行确定一个整数row(i),没列也确定一个正整数col（i），使得对于任意格子（i，j）,w(i,j) <= row(i)+col(j).所有row(i)和col(i)之和应最小
由w(i,j)<=row(i)+col(j) 使用km算法时在推导的时候有这样一个公式 Lx[i]+Ly[i]>=W[i][j], 且KM使得 Lx[i]+Ly[i]==W[i][j],那么可以转化为KM来计算。
每个row[i] 为Lx[i], 那么col[i]为Ly[i], w[i][j]为i和j连接的边的权重。
1 #include <algorithm> 2 #include <string.h> 3 #include <iostream> 4 #include <cstdio> 5 #include <cmath> 6 #include <vector> 7 using namespace std; 8 /* KM算法 9 * 复杂度O(nx*nx*ny) 10 * 求最大权匹配 11 * 若求最小权匹配，可将权值取相反数，结果取相反数 12 * 点的编号从0开始 13 */ 14 const int N = 505; 15 const int INF = 1000000; 16 int nx,ny; //两边的点数 17 int W[N][N]; //二分图描述 18 int Left[N],Lx[N],Ly[N]; //y中各点匹配状态 x,y中的点标号 19 int slack[N]; 20 bool S[N],T[N]; 21 vector<int> G[N]; 22 bool DFS(int x) { 23 S[x] = true; 24 for(int y = 0; y < ny; y++){ 25 if(T[y]) continue; 26 int tmp = Lx[x] + Ly[y] - W[x][y]; 27 if(tmp==0){ 28 T[y] = true; 29 if(Left[y] == -1 || DFS(Left[y])){ 30 Left[y] = x; 31 return true; 32 } 33 } 34 else if(slack[y] > tmp) 35 slack[y] = tmp; 36 } 37 return false; 38 } 39 void KM(){ 40 memset(Left, -1, sizeof(Left)); 41 memset(Ly,0, sizeof(Ly)); 42 for(int i = 0;i < nx;i++){ 43 Lx[i] = -INF; 44 for(int j = 0;j < ny;j++) 45 Lx[i] = max(Lx[i],W[i][j]); 46 } 47 for(int x = 0;x < nx;x++){ 48 for(int i = 0;i < ny;i++) 49 slack[i] = INF; 50 while(true){ 51 memset(S, false, sizeof(S)); 52 memset(T, false, sizeof(T)); 53 if(DFS(x)) break; 54 int d = INF; 55 for(int i = 0;i < ny;i++) 56 if(!T[i] && d > slack[i]) 57 d = slack[i]; 58 for(int i = 0;i < nx;i++) 59 if(S[i]) 60 Lx[i] -= d; 61 for(int i = 0;i < ny;i++){ 62 if(T[i])Ly[i] += d; 63 else slack[i] -= d; 64 } 65 } 66 } 67 } 68 //HDU 2255 69 double x1[N],x2[N],yy1[N],yy2[N]; 70 int main() 71 { 72 int n; 73 while(scanf("%d",&n) == 1){ 74 for(int i =0; i<n; i++){ 75 for(int j =0; j < n; ++j){ 76 scanf("%d",&W[i][j]); 77 } 78 } 79 nx = ny = n; 80 KM(); 81 int sum=0; 82 for(int i=0; i<n-1; i++) { printf("%d ",Lx[i]); sum+=Lx[i];} printf("%d ",Lx[n-1]); 83 for(int i=0; i<n-1; i++) { printf("%d ",Ly[i]); sum+=Ly[i];}printf("%d ",Ly[n-1]); 84 printf("%d ",sum+Lx[n-1]+Ly[n-1]); 85 } 86 return 0; 87 }