1070: [SCOI2007]修车

https://www.lydsy.com/JudgeOnline/problem.php?id=1070

分析：

　　每个第几次修车等的时间都不一样，当前第i个人修理的车的队列是a1,a2...ak，那么对于ak等待的时间就是前面所有车的修理时间之和。如果这样建图显然空间开不下。考虑换种建图方式，a1对于后面所有车的等待时间都会加上它的修理时间，每个修理的汽车，都会对后面所有修的车加上它的修理时间。

　　所以每个人拆成n个点，第i个点表示倒数第i个修的车，那么所有的花费都应乘以i。

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<cctype>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 #include<map>
11 #define fi(s) freopen(s,"r",stdin);
12 #define fo(s) freopen(s,"w",stdout);
13 using namespace std;
14 typedef long long LL;
15 
16 inline int read() {
17     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
18     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
19 }
20 
21 const int INF = 1e9;
22 const int N = 1005;
23 
24 struct Edge{
25     int u, to, nxt, f, c;
26     Edge () {} 
27     Edge (int _1,int _2,int _3,int _4,int _5) { u = _1, to = _2, f = _3, c = _4, nxt = _5; }
28 }e[100005];
29 int head[N], En = 1, S, T;
30 
31 namespace MaxflowMincost{
32     int pre[N], dis[N], q[100005], Maxflow, Mincost; // q[N]！！！ 
33     bool vis[N];
34     bool spfa() {
35         for (int i=1; i<=T; ++i) dis[i] = INF, vis[i] = false, pre[i] = 0;
36         int L = 1, R = 0;
37         q[++R] = S, dis[S] = 0, vis[S] = true, pre[S] = 0;
38         while (L <= R) {
39             int u = q[L ++]; vis[u] = false;
40             for (int i=head[u]; i; i=e[i].nxt) {
41                 int v = e[i].to;
42                 if (dis[v] > dis[u] + e[i].c && e[i].f > 0) {
43                     dis[v] = dis[u] + e[i].c;
44                     pre[v] = i;
45                     if (!vis[v]) q[++R] = v, vis[v] = true;
46                 }
47             }
48         }
49         return dis[T] != INF;
50     }
51     void mcf() {
52         int zf = INF;
53         for (int i=T; i!=S; i=e[pre[i]].u) 
54             zf = min(zf, e[pre[i]].f);
55         for (int i=T; i!=S; i=e[pre[i]].u) 
56             e[pre[i]].f -= zf, e[pre[i] ^ 1].f += zf;
57         Maxflow += zf, Mincost += dis[T] * zf;
58     }
59     void solve() {
60         Mincost = Maxflow = 0;
61         while (spfa()) 
62             mcf();
63     }
64 }
65 
66 void add_edge(int u,int v,int f,int c) {
67     ++En; e[En] = Edge(u, v, f, c, head[u]); head[u] = En;
68     ++En; e[En] = Edge(v, u, 0, -c, head[v]); head[v] = En;
69 }
70 
71 int main() {
72     int m = read(), n = read();
73     S = n + m * n + 1, T = S + 1;
74     
75     for (int i=1; i<=n; ++i) add_edge(S, i, 1, 0);
76     for (int i=1; i<=n; ++i) { // 第i辆车 
77         for (int j=1; j<=m; ++j) { // 第j个人 
78             int w = read();
79             for (int k=1; k<=n; ++k) // 第k次修 
80                 add_edge(i, j * n + k, 1, k * w); // i+n, j*n+k !!!
81         }
82     }
83     for (int i=n+1,lim=(n+m*n); i<=lim; ++i) add_edge(i, T, 1, 0);
84     
85     MaxflowMincost::solve();
86     int ans = MaxflowMincost::Mincost;
87     printf("%.2lf", (1.0 * ans) / (1.0 * n));
88     return 0;
89 }