[SCOI2007]修车费用流

题解：

因为我们并不需要知道准确方案，而人数固定，要使得平均等待时间最小，也就是要使得总的等待时间最小。

因此我们将工人按每个时刻拆点，拆完之后向车子连边，流量为1，费用为k * 维修时间（倒数第k个修，所以对时间的贡献就是k * 维修时间，因为后面的k-1人要等它，自己也要等）

那这样会不会导致有人不需要等这个工人（因为他去找别人帮他修车了），但我们还是计入了他的等待时间呢？

这是不可能的，因为这样就说明那k-1个人中其实有些人是不存在的，既然这些人不存在，那就没必要倒数第k个修，直接往后推变成倒数k-1,k-2……修不就行了？

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define R register int
  4 #define INF 2139062143
  5 #define AC 40000
  6 #define ACway 400000
  7 int n, m, s, t, tot = 1, ans, ansflow;
  8 int dis[AC], Head[AC], last[AC], disflow[AC];
  9 int date[ACway], Next[ACway], have[ACway], haveflow[ACway], cost[ACway];
 10 bool z[AC];
 11 deque <int> q;
 12 
 13 inline int read()
 14 {
 15     int x = 0; char c = getchar();
 16     while(c > '9' || c < '0') c = getchar();
 17     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
 18     return x; 
 19 }
 20 
 21 inline int Min(int a, int b)
 22 {
 23     if(a < b) return a;
 24     else return b;
 25 }
 26 
 27 void add(int f, int w, int S, int c)
 28 {
 29     //printf("%d ---> %d flow is %d , cost %d
",f,w,S,c);
 30     date[++tot] = w , Next[tot] = Head[f] , haveflow[tot] = S , cost[tot] = c , Head[f] = tot;
 31     date[++tot] = f , Next[tot] = Head[w] ,  cost[tot] = -c , Head[w] = tot;
 32 }
 33 
 34 void cal()
 35 {
 36     int x = t;
 37     if(dis[t] != INF)
 38     {
 39         while(x != s)
 40         {
 41             haveflow[last[x]] -= disflow[t];
 42             haveflow[last[x] ^ 1] += disflow[t];
 43             x = date[last[x] ^ 1];
 44         }
 45         ans += disflow[t] * dis[t];
 46     }
 47 }
 48 
 49 bool spfa()
 50 {
 51     int x, now;
 52     z[s] = true, dis[s] = 0, disflow[s] = INT_MAX;
 53     q.push_front(s);
 54     while(!q.empty())
 55     {
 56         x = q.front();
 57         q.pop_front();
 58         z[x] = false;
 59         for(R i = Head[x]; i ; i = Next[i])
 60         {
 61             now = date[i];
 62             if(haveflow[i] && dis[now] > dis[x] + cost[i])
 63             {
 64                 dis[now] = dis[x] + cost[i];
 65                 last[now] = i;
 66                 disflow[now] = Min(disflow[x], haveflow[i]);
 67                 if(!z[now] && now != t)//t就不要加进来的了
 68                 {
 69                     if(!q.empty() && dis[now] < dis[q.front()]) q.push_front(now);
 70                     else q.push_back(now);
 71                     z[now] = true;
 72                 }
 73             }
 74         }
 75     }
 76     cal();
 77     return dis[t] != INF;
 78 }
 79 
 80 void pre()
 81 {
 82     R a;
 83     m = read(), n = read();
 84     s = n + n * m + 1;
 85     t = s + 1;
 86     for(R i = 1; i <= n; i++)
 87         for(R j = 1; j <= m; j++)
 88         {
 89             a = read();
 90             for(R k = 1; k <= n; k++)
 91                 add(i, n + (j - 1) * n + k, 1, k * a);//将每个工人分成n个，分别代表n个时刻(以车记)    
 92         }
 93     for(R i = 1; i <= n; i++) add(s, i, 1, 0);
 94     for(R i = n + 1; i <= n + n * m; i++) add(i, t, 1, 0);
 95 }
 96 
 97 void work()
 98 {
 99     memset(dis, 0x7f, sizeof(dis));
100     while(spfa())
101         memset(dis, 0x7f, sizeof(dis));
102     printf("%.2lf
", (double)ans / (double)n);
103 }
104 
105 int main()
106 {
107 //    freopen("in.in","r",stdin);
108     pre();
109     work();
110   //  fclose(stdin);
111     return 0;
112 }

[SCOI2007]修车 费用流

[SCOI2007]修车费用流