1070: [SCOI2007]修车

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

分析：

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

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

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cctype>

 #include<set>

 #include<vector>

 #include<queue>

 #include<map>

 #define fi(s) freopen(s,"r",stdin);

 #define fo(s) freopen(s,"w",stdout);

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int INF = 1e9;

 const int N = ;

 struct Edge{

     int u, to, nxt, f, c;

     Edge () {}

     Edge (int _1,int _2,int _3,int _4,int _5) { u = _1, to = _2, f = _3, c = _4, nxt = _5; }

 }e[];

 int head[N], En = , S, T;

 namespace MaxflowMincost{

     int pre[N], dis[N], q[], Maxflow, Mincost; // q[N]！！！

     bool vis[N];

     bool spfa() {

         for (int i=; i<=T; ++i) dis[i] = INF, vis[i] = false, pre[i] = ;

         int L = , R = ;

         q[++R] = S, dis[S] = , vis[S] = true, pre[S] = ;

         while (L <= R) {

             int u = q[L ++]; vis[u] = false;

             for (int i=head[u]; i; i=e[i].nxt) {

                 int v = e[i].to;

                 if (dis[v] > dis[u] + e[i].c && e[i].f > ) {

                     dis[v] = dis[u] + e[i].c;

                     pre[v] = i;

                     if (!vis[v]) q[++R] = v, vis[v] = true;

                 }

             }

         }

         return dis[T] != INF;

     }

     void mcf() {

         int zf = INF;

         for (int i=T; i!=S; i=e[pre[i]].u)

             zf = min(zf, e[pre[i]].f);

         for (int i=T; i!=S; i=e[pre[i]].u)

             e[pre[i]].f -= zf, e[pre[i] ^ ].f += zf;

         Maxflow += zf, Mincost += dis[T] * zf;

     }

     void solve() {

         Mincost = Maxflow = ;

         while (spfa())

             mcf();

     }

 }

 void add_edge(int u,int v,int f,int c) {

     ++En; e[En] = Edge(u, v, f, c, head[u]); head[u] = En;

     ++En; e[En] = Edge(v, u, , -c, head[v]); head[v] = En;

 }

 int main() {

     int m = read(), n = read();

     S = n + m * n + , T = S + ;

     for (int i=; i<=n; ++i) add_edge(S, i, , );

     for (int i=; i<=n; ++i) { // 第i辆车

         for (int j=; j<=m; ++j) { // 第j个人

             int w = read();

             for (int k=; k<=n; ++k) // 第k次修

                 add_edge(i, j * n + k, , k * w); // i+n, j*n+k !!!

         }

     }

     for (int i=n+,lim=(n+m*n); i<=lim; ++i) add_edge(i, T, , );

     MaxflowMincost::solve();

     int ans = MaxflowMincost::Mincost;

     printf("%.2lf", (1.0 * ans) / (1.0 * n));

     return ;

 }