|
|
题目大意：
有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>
3using namespace std;
4
5int n,m;
6int a[55][2505];
7int lx[55],ly[2505];
8bool x[55],y[2505];
9int match[2505];
10
11void 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
25bool 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
40int 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
80int 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
|