bzoj 1070 [SCOI2007]修车

Description

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

Input

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

Output

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

Sample Input

2 2

3 2

1 4

Sample Output

1.50

HINT

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

题解

工人i修第j台车的时间为time(i,j)，把每个工人拆成n个，对于工人i的第j个点表示工人i倒数第j个修的处理点，记为p(i,j)；

S向每个人连容量为1、边权为0的边，对于第i个人，向(j,k)连容量为1、边权tim[j][i]*k的边，最小费用最大流即为答案。

因为我们难以确定一个点被其他点的“影响程度”，换个思路，考虑当前点对于别的点造成的影响，很容易发现，如果当前车在当前工人这里倒数第k个修理，那么对全局产生的贡献就是k*time，这样一来就可以直接处理每个点的贡献了。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define N 40010
#define inf 0x33333333
using namespace std;
typedef pair<int, int> Pair;
struct MFMC {
    struct node {
        int from, to, next, flow, cost;
    }e[N * 10];
    int tot, st[N], pe[N], pv[N], dis[N], vis[N];
    void init() {
        tot = -1, memset(e, -1, sizeof e);
        memset(st, -1, sizeof st);
    }
    void add(int x, int y, int z, int zz) {
        e[++tot].to = y, e[tot].from = x;
        e[tot].flow = z, e[tot].cost = zz;
        e[tot].next = st[x], st[x] = tot;
    }
    void add_edge(int x, int y, int z, int zz) {
        add(x, y, z, zz), add(y, x, 0, -zz);
    }
    queue <int> que;
    bool spfa(int S, int T) {
        memset(dis, 0x33, sizeof dis);
        memset(vis, 0, sizeof vis);
        que.push(S), vis[S] = 1, dis[S] = 0;
        while(!que.empty()) {
            int now = que.front();
            que.pop();
            vis[now] = 0;
            for (int i = st[now]; ~i; i = e[i].next)
                if (e[i].flow > 0 && dis[e[i].to] > dis[now] + e[i].cost) {
                    dis[e[i].to] = dis[now] + e[i].cost;
                    pe[e[i].to] = i, pv[e[i].to] = now;
                    if (!vis[e[i].to])
                        vis[e[i].to] = 1, que.push(e[i].to);
                }
        }
        return dis[T] < inf;
    }
    Pair mfmc(int S, int T) {
        int COST = 0, FLOW = 0, flow;
        while(spfa(S, T)) {
            flow = inf;
            for (int i = T; i != S; i = pv[i])
                flow = min(flow, e[pe[i]].flow);
            COST += flow * dis[T];
            FLOW += flow;
            for (int i = T; i != S; i = pv[i])
                e[pe[i]].flow -= flow, e[pe[i] ^ 1].flow += flow;
        }
        return make_pair(FLOW, COST);
    }
}mcmf;
int n, m, time[100][100];
main() {
    scanf("%d%d", &m, &n);
    mcmf.init();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &time[i][j]);
    int S = n * m + n + 1, T = S + 1;
    for (int i = 1; i <= n; ++i)
        mcmf.add_edge(S, n * m + i, 1, 0);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            for (int k = 1; k <= n; ++k)
                mcmf.add_edge(n * m + i, (j - 1) * n + k, 1, time[i][j] * k);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            mcmf.add_edge((j - 1) * n + i, T, 1, 0);
    Pair ans = mcmf.mfmc(S, T);
    printf("%.2lf\n", (double)ans.second/(double)n);
}