引用：
[PKU][POJ][3686][THE WINDY'S]
本题的建图方法很有意思, 我解这题的思维过程也挺有意思.
刚看到这题, 因为才做过[PKU][2516], 马上想到了带权二分匹配, 并且工厂和任务是一对多的关系, 很可能是要拆点, 把工厂拆开来. 于是马上开始敲键盘, 以订单为X集, 订单i在工厂j完成为Y集建图, 代码敲了几行感觉有点不对劲, 于是回过头再去看看题目要求什么, 一看果然是理解错了, 题目要求的是完成时间的平均值, 而不是生产时间的平均值, 完成时间还包括了等待的时间.
嗯, 那么Y集的状态应该改改, 既然主线是转化成带权二分匹配, 而且按这个数据规模来看不可能两边都是2500的顶点, 肯定有一边是50, 另一边是50或2500, 那么最后只有50条边被选中, 因为二分匹配中的每条边最多只累计一次, 所以不会产生"累加"的效果, 所以这50条边每条都必须能完全独立地表达"某订单在某工厂耗费的总时间". 第一反应当然是想把Y集顶点表示工厂j第k个订单, 当然这肯定是不对的, 前k-1个任务根本不能确定, 那这条边又怎么能完全独立地表达"某订单在某工厂耗费的总时间"呢?
再回到题目中去, 他要求平均时间, 就是总时间除n, 我们要求的是总时间, 总时间可以表示成每笔订单各自的完成时间相加, 把每笔订单各自的完成时间再写出来, 就是它之前的所有订单的生产时间加上它自己的生产时间, 而它之前的一个任务的完成时间再拆开来看…为什么要把每个订单的完成时间看成一个整体呢? 换个思路, 若订单i在厂j完成后, 后面还有k个任务, 那么这个总时间就还要加上k份i的生产时间. 那么就把Y集顶点表示成工厂j完成倒数第k个好了, 这样就把每笔订单的生产时间以及延误其他订单的时间看成一个整体(生产时间又可以看成是延误自己的时间). 后面就是套KM模板的事情了.
代码：
1 Source Code
2
3 Problem: 3686 User: yzhw
4 Memory: 1024K Time: 16MS
5 Language: G++ Result: Accepted
6 Source Code
7 # include <cstdio>
8 # include <cstring>
9 using namespace std;
10 # define max(a,b) ((a)>(b)?(a):(b))
11 # define min(a,b) ((a)<(b)?(a):(b))
12 # define N 55
13 # define M 3000
14 int val[N][M],n,m,ln[N],rn[M],match[M];
15 bool l[N],r[M];
16 bool dfs(int pos)
17 {
18 l[pos]=true;
19 for(int i=0;i<n*m;i++)
20 if(!r[i]&&ln[pos]+rn[i]==val[pos][i])
21 {
22 r[i]=true;
23 if(match[i]==-1||dfs(match[i]))
24 {
25 match[i]=pos;
26 return true;
27 }
28 }
29 return false;
30 }
31 void adjust()
32 {
33 int minnum=0xfffffff;
34 for(int i=0;i<n;i++)
35 if(l[i])
36 for(int j=0;j<n*m;j++)
37 if(!r[j])
38 minnum=min(minnum,ln[i]+rn[j]-val[i][j]);
39 for(int i=0;i<n;i++)
40 if(l[i]) ln[i]-=minnum;
41 for(int i=0;i<n*m;i++)
42 if(r[i]) rn[i]+=minnum;
43
44 }
45 int main()
46 {
47 int test;
48 scanf("%d",&test);
49 while(test--)
50 {
51 scanf("%d%d",&n,&m);
52 for(int i=0;i<n;i++)
53 for(int j=0;j<m;j++)
54 {
55 scanf("%d",&val[i][j]);
56 val[i][j]*=-1;
57 }
58 for(int k=1;k<=n;k++)
59 for(int i=0;i<n;i++)
60 for(int j=0;j<m;j++)
61 val[i][(k-1)*m+j]=k*val[i][j];
62 memset(rn,0,sizeof(rn));
63 for(int i=0;i<n;i++)
64 {
65 int maxnum=-0xfffffff;
66 for(int j=0;j<n*m;j++)
67 maxnum=max(maxnum,val[i][j]);
68 ln[i]=maxnum;
69 }
70 memset(match,-1,sizeof(match));
71 for(int i=0;i<n;i++)
72 {
73 memset(l,0,sizeof(l));
74 memset(r,0,sizeof(r));
75 while(!dfs(i))
76 {
77 adjust();
78 memset(l,0,sizeof(l));
79 memset(r,0,sizeof(r));
80 }
81 }
82 int total=0;
83 for(int i=0;i<n*m;i++)
84 if(match[i]!=-1)
85 total-=val[match[i]][i];
86 printf("%.6f\n",(double)total/n);
87 }
88 return 0;
89 }