[费用流][BZOJ1070]修车

修车

题目描述

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

输入

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

输出

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

样例输入

2 2
3 2
1 4

样例输出

1.50

提示

2<=M<=9,1<=N<=60 , 1<=T<=1000

又是一题看题解过的题...费用流难哇qaqq

对于每一个修车♂师傅，拆成N个点表示修N辆车

把车和所有的修车师傅拆成的N * M个点连边，记A[i, j]为第i个师傅修倒数第j辆车,流量为1（每辆车只能被修♂一次），费用为time[i , j] * k

关于费用：因为第j辆车在倒数第k个被修因此对全局产生的费用为time[i, j] * k （通俗的来说就是后面的人要排队啦w

S连每辆车，费用为0流量为1，每个师傅拆成的点连T，费用为0流量为1。

然后跑一遍MCMF结果除以k就好啦owo

代码：

  1 #include<algorithm>
  2 #include<cstdio>
  3 #include<cstring>
  4  
  5 const int Maxv = 1010, inf = 0x6ffffff, T = 1001; 
  6 int Next[Maxv], Head[Maxv], from[Maxv], tim[61][10], w[Maxv], v[Maxv], q[Maxv], d[Maxv], ans, cnt = 1, n, m; 
  7 bool inq[Maxv]; 
  8 struct edge{
  9     int from, to, next, c, v;
 10 }e[100001]; 
 11  
 12 int read(){
 13     int x = 0, f = 1; 
 14     char c = getchar(); 
 15     while (c < '0' || c > '9') {
 16         if (c == '-') {
 17             f = -1; 
 18         }
 19         c = getchar(); 
 20     }
 21     while(c >= '0' && c <= '9') {
 22         x = x * 10 + c - '0'; 
 23         c = getchar(); 
 24     }
 25     return x * f; 
 26 }
 27  
 28 void Add(int u, int v, int w, int c) {
 29     cnt++; 
 30     e[cnt].next = Head[u]; 
 31     e[cnt].to = v; 
 32     e[cnt].from = u; 
 33     e[cnt].c = c; 
 34     e[cnt].v = w;  
 35     Head[u] = cnt; 
 36 }
 37  
 38 void Add_Edge(int u, int v, int w, int c) {
 39     Add(u, v, w, c); 
 40     Add(v, u, 0, -c); 
 41 }
 42  
 43 bool spfa()
 44 {
 45     for (int i = 0; i <= T; i++) {
 46         d[i] = inf;
 47     }
 48     int t = 0, w = 1;
 49     d[0] = 0;
 50     inq[0] = true;
 51     q[0] = 0;
 52     while(t != w) {
 53         int now = q[t];
 54         t++;
 55         if(t == T) {
 56             t = 0;
 57         }
 58         for (int i = Head[now]; i; i = e[i].next) {
 59             if (e[i].v && d[e[i].to] > d[now] + e[i].c) {
 60                 d[e[i].to] = d[now] + e[i].c;
 61                 from[e[i].to] = i;
 62                 if (!inq[e[i].to]) {
 63                     inq[e[i].to] = true;
 64                     q[w++] = e[i].to;
 65                     if(w == T) {
 66                         w = 0;
 67                     }
 68                 } 
 69             }
 70         }
 71         inq[now] = false; 
 72     }
 73     if (d[T] == inf) {
 74         return false;
 75     }
 76     return true;
 77 }
 78  
 79 void mcf()
 80 {
 81     int x = inf;
 82     for (int i = from[T]; i; i = from[e[i].from]) {
 83         x = std::min(x, e[i].v);
 84     }
 85     for (int i = from[T]; i; i = from[e[i].from]) {
 86         e[i].v -= x;
 87         e[i ^ 1].v += x;
 88         ans += e[i].c * x;
 89     }
 90 }
 91  
 92 int main(){
 93     n = read(); 
 94     m = read(); 
 95     for (int i = 1; i <= m; i++) {
 96         for (int j = 1; j <= n; j++) {
 97             tim[i][j] = read(); 
 98         }
 99     }
100     for (int i = 1; i <= n * m; i++) {
101         Add_Edge(0, i, 1, 0); 
102     }
103     for (int i = n * m + 1; i <= n * m + m; i++) {
104         Add_Edge(i, T, 1, 0); 
105     }
106     for (int i = 1; i <= n; i++) {
107         for (int j = 1; j <= m; j++) {
108             for (int k = 1; k <= m; k++) {
109                 Add_Edge((i - 1) * m + j, n * m + k, 1, tim[k][i] * j);
110             }
111         }
112     }
113     while (spfa()) {
114         mcf();
115     }
116     printf("%.2lf", (double)ans / m);
117     return 0;
118 }