同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同
的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最
小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

　　第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人
员维修第i辆车需要用的时间T。

　　最小平均等待时间，答案精确到小数点后2位。

数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)

  1 #include <bits/stdc++.h>  2   3 #define fread_siz 1024  4   5 inline int get_c(void)  6 {  7     static char buf[fread_siz];  8     static char *head = buf + fread_siz;  9     static char *tail = buf + fread_siz; 10  11     if (head == tail) 12         fread(head = buf, 1, fread_siz, stdin); 13  14     return *head++; 15 } 16  17 inline int get_i(void) 18 { 19     register int ret = 0; 20     register int neg = false; 21     register int bit = get_c(); 22  23     for (; bit < 48; bit = get_c()) 24         if (bit == ‘-‘)neg ^= true; 25  26     for (; bit > 47; bit = get_c()) 27         ret = ret * 10 + bit - 48; 28  29     return neg ? -ret : ret; 30 } 31  32 template <class T> 33 inline T min(T a, T b) 34 { 35     return a < b ? a : b; 36 } 37  38 const int maxn = 500005; 39 const int inf = 0x3f3f3f3f; 40  41 int n, m; 42 int s, t; 43 int cost; 44 int edges; 45 int hd[maxn]; 46 int to[maxn]; 47 int nt[maxn]; 48 int vl[maxn]; 49 int fl[maxn]; 50  51 inline void add_edge(int u, int v, int f, int w) 52 {     53     nt[edges] = hd[u]; to[edges] = v; fl[edges] = f; vl[edges] = +w; hd[u] = edges++; 54     nt[edges] = hd[v]; to[edges] = u; fl[edges] = 0; vl[edges] = -w; hd[v] = edges++; 55 } 56  57 inline bool bfs(void) 58 { 59     static int dis[maxn]; 60     static int que[maxn]; 61     static int inq[maxn]; 62     static int pre[maxn]; 63     static int head, tail; 64      65     memset(inq, 0, sizeof(inq)); 66     memset(dis, inf, sizeof(dis)); 67      68     head = 0, tail = 0; 69     que[tail++] = s; 70     pre[s] = -1; 71     dis[s] = 0; 72     inq[s] = 1; 73      74     while (head != tail) 75     { 76         int u = que[head++], v; inq[u] = 0; 77          78         if (head >= maxn) 79             head = 0; 80          81         for (int i = hd[u]; ~i; i = nt[i]) 82             if (fl[i] && dis[v = to[i]] > dis[u] + vl[i]) 83             { 84                 dis[v] = dis[u] + vl[i], pre[v] = i^1;  85                 if (!inq[v]) 86                     inq[v] = 1, que[tail++] = v; 87                 if (tail >= maxn) 88                     tail = maxn; 89             } 90     } 91  92     if (dis[t] >= inf) 93         return false; 94          95     int flow = inf; 96      97     for (int i = pre[t]; ~i; i = pre[to[i]]) 98         if (flow > fl[i ^ 1]) 99             flow = fl[i ^ 1];100             101     for (int i = pre[t]; ~i; i = pre[to[i]])102         fl[i] += flow, fl[i ^ 1] -= flow;103         104     cost += flow * dis[t];105         106     return true;107 }108 109 inline void max_flow(void)110 {111     while (bfs());112 }113 114 signed main(void)115 {116     n = get_i();117     m = get_i();118     119     s = 0, t = n*m + m + 1;120     121     memset(hd, -1, sizeof(hd));122     123     for (int i = 1; i <= n*m; ++i)124         add_edge(s, i, 1, 0);125     126     for (int i = 1; i <= m; ++i)127         add_edge(i + n*m, t, 1, 0);128         129     for (int i = 1; i <= m; ++i)130         for (int j = 1; j <= n; ++j)131         {132             int w = get_i();133             for (int k = 1; k <= m; ++k)134                 add_edge((j - 1)*m + k, n*m + i, 1, w*k); 135         }136         137     max_flow();138     139     printf("%.2f\n", (float)cost / m);140 }