题意：就是有m个人去n银行告诉你每个人去每个银行的速度让你求每个银行都去人平均时间最少的方案。人比银行多。
思路：加一个源点指向所有人（费用0流量1）加一个汇点所有银行指向他（费用0流量1）。这样就转化成最小费用最大流问题。用模版搞定即可。
这题一开始自己死活过不了，看了解题报告发现结果要加eps不然就是过不了0.0我的程序eps从1e-3--1e-9都可以。
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <queue> 8 #include <stack> 9 #include <vector> 10 #include <utility> 11 #define LEN 510 12 #define ll long long 13 #define eps 1e-3 14 #define INF 0x3f3f3f3f 15 16 using namespace std; 17 18 double cost[LEN][LEN]; 19 int cap[LEN][LEN], n; 20 21 void init() 22 { 23 memset(cost, 0x3f, sizeof cost); 24 memset(cap, 0, sizeof cap); 25 } 26 27 int minCostMaxflow(int s, int t, double &c){ 28 int f, flow[LEN][LEN], p[LEN]; 29 double d[LEN]; 30 queue<int> q; 31 memset(flow, 0, sizeof flow); 32 c = f = 0; 33 while(1) 34 { 35 bool inq[LEN]; 36 for(int i=0; i<n; i++) d[i] = (i==s?0:INF); 37 memset(inq, 0, sizeof inq); 38 q.push(s); 39 while(!q.empty()){ 40 int u = q.front();q.pop(); 41 inq[u] = false; 42 for(int v=0; v < n; v++){ 43 if(cap[u][v]>flow[u][v] && d[v]>d[u]+cost[u][v]){ 44 d[v] = d[u]+cost[u][v]; 45 p[v] = u; 46 if(!inq[v]){ 47 inq[v] = true; 48 q.push(v); 49 } 50 } 51 } 52 } 53 if(fabs(d[t]-INF)<eps)break; 54 int a = INF; 55 for(int u=t; u!=s; u = p[u]){ 56 a = min(a, cap[p[u]][u]-flow[p[u]][u]); 57 } 58 for(int u=t; u!=s; u = p[u]){ 59 flow[p[u]][u]+=a; 60 flow[u][p[u]]-=a; 61 } 62 c+=d[t]*a; 63 f+=a; 64 } 65 return f; 66 } 67 68 int main() 69 { 70 // freopen("in.txt", "r", stdin); 71 72 int a, b; 73 while(scanf("%d%d", &a, &b)!=EOF){ 74 if(!a && !b)break; 75 init(); 76 for(int i=0; i<a; i++){ 77 for(int j=0; j<b; j++){ 78 scanf("%lf", &cost[j][b+i]); 79 cost[b+i][j] = -cost[j][b+i]; 80 cap[j][b+i] = 1; 81 } 82 } 83 n = a+b+2; 84 for(int i=0; i<b; i++){ 85 cap[n-2][i] = 1; 86 cost[n-2][i] = 0; 87 } 88 for(int i=0; i<a; i++){ 89 cap[b+i][n-1] = 1; 90 cost[b+i][n-1] = 0; 91 } 92 double c; 93 int ans = minCostMaxflow(n-2, n-1, c); 94 printf("%.2lf ", (c/a)+eps); 95 } 96 return 0; 97 }