引用：
[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 }