|
题目大意: 有N个工件要在M个机器上加工,有一个N*M的矩阵描述其加工时间。 同一时间内每个机器只能加工一个工件,问加工完所有工件后,使得平均加工时间最小。
将工件作为二分图中X部的点,总共N个。
将每个机器拆成N个点作为二分图中Y部的点,总共N*M个。
第J个机器的第P个点代表,使用机器 J进行倒数第P次加工。
假设我们按顺序在J机器上工件I1,I2,I3..IK个工件,则总共需要花费I1*K+I2*(K- 1)+I3*(K-3)+ +IK。
所以我们对于X中每个点I,Y中每个点(J,P),连接一条A[I,J]*P权值的边。
接下来进行二分图最佳匹配即可。这里有一篇介绍KM算法比较详细的文章:http://www.cnblogs.com/zhuangli/archive/2008/08/03/1259248.html
  1 #include<iostream> 2 #include<cmath> 3 using namespace std; 4 5 int n,m; 6 int a[55][2505]; 7 int lx[55],ly[2505]; 8 bool x[55],y[2505]; 9 int match[2505]; 10 11 void init() 12  { 13 int k; 14 cin>>n>>m; 15 16 for(int i=1;i<=n;i++) { 17 for(int j=1;j<=m;j++) { 18 cin>>k; 19 for(int p=1;p<=n;p++) 20 a[i][(p-1)*m+j]=-k*p; //拆点 21 } 22 } 23 } 24 25 bool dfs(int k) 26  { 27 x[k]=true; 28 for(int i=1;i<=n*m;i++) { 29 if(!y[i]&&lx[k]+ly[i]==a[k][i]) { 30 y[i]=true; 31 if(!match[i]||dfs(match[i])) { 32 match[i]=k; 33 return true; 34 } 35 } 36 } 37 return false; 38 } 39 40 int km() 41  { 42 int i,j,k; 43 44 for(i=1;i<=n;i++) { //将lx[i]初始化为与i相连的最大边的权值 45 lx[i]=-INT_MAX; 46 for(j=1;j<=n*m;j++) 47 lx[i]=max(lx[i],a[i][j]); 48 } 49 memset(match,0,sizeof(match)); 50 memset(ly,0,sizeof(ly)); //初始化ly[]为0 51 for(i=1;i<=n;i++) { 52 53 while(1) { 54 memset(x,false,sizeof(x)); 55 memset(y,false,sizeof(y)); 56 if(dfs(i)) break; 57 58 int dx=INT_MAX; 59 for(j=1;j<=n;j++) { 60 if(x[j]) { 61 for(k=1;k<=n*m;k++) { 62 if(!y[k]) { 63 dx=min(dx,lx[j]+ly[k]-a[j][k]); 64 } 65 } 66 } 67 } //更新lx[]和ly[] 68 for(j=1;j<=n;j++) 69 if(x[j]) lx[j]-=dx; 70 for(j=1;j<=n*m;j++) 71 if(y[j]) ly[j]+=dx; 72 } 73 } 74 int ans=0; 75 for(i=1;i<=n*m;i++) 76 ans+=a[match[i]][i]; 77 return -ans; 78 } 79 80 int main() 81  { 82 int t; 83 cin>>t; 84 while(t--) { 85 init(); 86 double ans=1.0*km()/n; 87 printf("%.6lf\n",ans); 88 } 89 return 0; 90 } 91 92 93
|