题意：一个工厂接到了N张订单。他们有M个车间，如果第i张单在第j个车间加工需要花费Zij的时间。现在给出这个Z的矩阵，问做完这N张单需要时间的平均值（总时间/N）包括等待时间。（比如说我在一个车间连续以1个时间单位接了3张单，那么总时间为1+2+3=6，平均值为6/3=2）(N,M<=50)
给了5000ms。假设第i个单子在第j个车间倒数第k个被加工，那么对应总时间会增加k*Zij。那么接下来的做法就显而易见了，拆下点，将(车间号,倒数第k个加工的席位)作为点来建图，从订单i向这些点连边，边权为k*Zij。KM或者费用流都可以上。ZKWflow跑了1000MS，普通的费用流跑了2000+MS，KM可以跑到0MS。。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <queue> 6 #define maxn 2600 7 #define maxm 1000000 8 #define INF 1<<30 9 using namespace std; 10 11 struct ZKW_flow{ 12 int src,sink,e,n; 13 int first[maxn]; 14 int cap[maxm],cost[maxm],v[maxm],next[maxm]; 15 void init(){ 16 e = 0; 17 memset(first,-1,sizeof(first)); 18 } 19 20 void add_edge(int a,int b,int cc,int ww){ 21 cap[e] = cc;cost[e] = ww;v[e] = b; 22 next[e] = first[a];first[a] = e++; 23 cap[e] = 0;cost[e] = -ww;v[e] = a; 24 next[e] = first[b];first[b] = e++; 25 } 26 27 int d[maxn]; 28 29 void spfa(){ 30 for(int i = 1;i <= n;i++) d[i] = INF; 31 priority_queue<pair<int,int> > q; 32 d[src] = 0; 33 q.push(make_pair(0,src)); 34 while(!q.empty()){ 35 int u = q.top().second,dd = -q.top().first; 36 q.pop(); 37 if(d[u] != dd) continue; 38 for(int i = first[u];i != -1;i = next[i]){ 39 if(cap[i] && d[v[i]] > dd + cost[i]){ 40 d[v[i]] = dd + cost[i]; 41 q.push(make_pair(-d[v[i]],v[i])); 42 } 43 } 44 } 45 for(int i = 1;i <= n;i++) d[i] = d[sink] - d[i]; 46 } 47 48 int Mincost,Maxflow; 49 bool used[maxn]; 50 51 int add_flow(int u,int flow){ 52 if(u == sink){ 53 Maxflow += flow; 54 Mincost += d[src] * flow; 55 return flow; 56 } 57 used[u] = true; 58 int now = flow; 59 for(int i = first[u];i != -1;i = next[i]){ 60 int &vv = v[i]; 61 if(cap[i] && !used[vv] && d[u] == d[vv] + cost[i]){ 62 int tmp = add_flow(vv,min(now,cap[i])); 63 cap[i] -= tmp; 64 cap[i^1] += tmp; 65 now -= tmp; 66 if(!now) break; 67 } 68 } 69 return flow - now; 70 } 71 72 bool modify_label(){ 73 int dd = INF; 74 for(int u = 1;u <= n;u++) if(used[u]) 75 for(int i = first[u];i != -1;i = next[i]){ 76 int &vv = v[i]; 77 if(cap[i] && !used[vv]) dd = min(dd,d[vv] + cost[i] - d[u]); 78 } 79 if(dd == INF) return false; 80 for(int i = 1;i <= n;i++) if(used[i]) d[i] += dd; 81 return true; 82 } 83 84 int min_cost_flow(int ss,int tt,int nn){ 85 src = ss,sink = tt,n = nn; 86 Mincost = Maxflow = 0; 87 spfa(); 88 while(1){ 89 while(1){ 90 for(int i = 1;i <= n;i++) used[i] = 0; 91 if(!add_flow(src,INF)) break; 92 } 93 if(!modify_label()) break; 94 } 95 return Mincost; 96 } 97 }; 98 99 ZKW_flow g; 100 101 int main(){ 102 int kase,n,m,z; 103 scanf("%d",&kase); 104 while(kase--){ 105 g.init(); 106 scanf("%d%d",&n,&m); 107 int S = n+n*m+1,T = n+n*m+2; 108 for(int i = 1;i <= n;i++) g.add_edge(S,i,1,0); 109 for(int i = 1;i <= n*m;i++) g.add_edge(i+n,T,1,0); 110 for(int i = 1;i <= n;i++){ 111 for(int j = 1;j <= m;j++){ 112 scanf("%d",&z); 113 for(int k = 1;k <= n;k++) g.add_edge(i,n+(j-1)*n+k,1,k*z); 114 } 115 } 116 int ans = g.min_cost_flow(S,T,T); 117 printf("%.6f ",(ans+0.0)/n); 118 } 119 return 0; 120 }