引用：
[PKU][POJ][3686][THE WINDY'S]
本題的建圖方法很有意思, 我解這題的思維過程也挺有意思.
剛看到這題, 因為才做過[PKU][2516], 馬上想到了帶權(quán)二分匹配, 并且工廠和任務(wù)是一對多的關(guān)系, 很可能是要拆點, 把工廠拆開來. 于是馬上開始敲鍵盤, 以訂單為X集, 訂單i在工廠j完成為Y集建圖, 代碼敲了幾行感覺有點不對勁, 于是回過頭再去看看題目要求什么, 一看果然是理解錯了, 題目要求的是完成時間的平均值, 而不是生產(chǎn)時間的平均值, 完成時間還包括了等待的時間.
嗯, 那么Y集的狀態(tài)應(yīng)該改改, 既然主線是轉(zhuǎn)化成帶權(quán)二分匹配, 而且按這個數(shù)據(jù)規(guī)模來看不可能兩邊都是2500的頂點, 肯定有一邊是50, 另一邊是50或2500, 那么最后只有50條邊被選中, 因為二分匹配中的每條邊最多只累計一次, 所以不會產(chǎn)生"累加"的效果, 所以這50條邊每條都必須能完全獨立地表達"某訂單在某工廠耗費的總時間". 第一反應(yīng)當(dāng)然是想把Y集頂點表示工廠j第k個訂單, 當(dāng)然這肯定是不對的, 前k-1個任務(wù)根本不能確定, 那這條邊又怎么能完全獨立地表達"某訂單在某工廠耗費的總時間"呢?
再回到題目中去, 他要求平均時間, 就是總時間除n, 我們要求的是總時間, 總時間可以表示成每筆訂單各自的完成時間相加, 把每筆訂單各自的完成時間再寫出來, 就是它之前的所有訂單的生產(chǎn)時間加上它自己的生產(chǎn)時間, 而它之前的一個任務(wù)的完成時間再拆開來看…為什么要把每個訂單的完成時間看成一個整體呢? 換個思路, 若訂單i在廠j完成后, 后面還有k個任務(wù), 那么這個總時間就還要加上k份i的生產(chǎn)時間. 那么就把Y集頂點表示成工廠j完成倒數(shù)第k個好了, 這樣就把每筆訂單的生產(chǎn)時間以及延誤其他訂單的時間看成一個整體(生產(chǎn)時間又可以看成是延誤自己的時間). 后面就是套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 }