题目地址：洛谷：【P2053】[SCOI2007]修车 – 洛谷、BZOJ：Problem 1070. — [SCOI2007]修车

题目描述

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

输入输出格式

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

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

输入输出样例

输入样例#1：

2 2
3 2
1 4

输出样例#1：

1.50

说明

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

题解

考虑使用最小费用最大流。我们需要考虑1.车的顺序2.修车的人，那么考虑把两个状态放在一起拆点，即让某个点代表顺序第几位修车人是谁的含义。这样，实际上我们就是在求二分图的最小权匹配了。权值的计算要考虑到这个位置对答案的贡献，显然倒数第i个修车的时间会对i个人的等待时间产生贡献，因此不妨把状态转成倒数第几位修车人是谁，这样权值就变成了产生贡献的人数*修车时间。
注意这里这些工人是可以同时开工的，也就是说，可以把车对应到同一时间的不同工人上。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

#include <vector>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, cap, cost, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap, int cost) {
    gra[tot] = Edge {v, cap, cost, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, -cost, head[v]}; head[v] = tot++;
}

int flow, cost, pre[MAXN], pree[MAXN], f[MAXN], dis[MAXN];
bool inque[MAXN];
std::queue<int> que;

inline void mcmf(int s, int t) {
    for(;;) {
        memset(f, 0, sizeof(f));
        memset(dis, 0x3f, sizeof(dis));
        dis[s] = 0; f[s] = INF; inque[s] = true; que.push(s);
        while(!que.empty()) {
            int u = que.front(); que.pop(); inque[u] = false;
            for(int i = head[u]; ~i; i = gra[i].nxt) {
                int v = gra[i].to;
                if(gra[i].cap > 0 && dis[v] > dis[u] + gra[i].cost) {
                    pre[v] = u; pree[v] = i;
                    f[v] = std::min(f[u], gra[i].cap);
                    dis[v] = dis[u] + gra[i].cost;
                    if(!inque[v]) {
                        inque[v] = true; que.push(v);
                    }
                }
            }
        }
        if(f[t] == 0) break;
        for(int i = t; i != s; i = pre[i]) {
            gra[pree[i]].cap -= f[t]; gra[pree[i] ^ 1].cap += f[t];
        }
        flow += f[t]; cost += f[t] * dis[t];
    }
}

int n, m, t[70][70], S, T;

// 1~n car
// n+1~mn+n staff
// mn+n+1 s mn+n+2 t
int main() {
    memset(head, -1, sizeof(head));
    m = readint(); n = readint();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            t[i][j] = readint();
        }
    }
    S = m * n + n + 1; T = S + 1;
    for(int i = 1; i <= n; i++) {
        addedge(S, m * n + i, 1, 0);
    }
    for(int i = 1; i <= m; i++) { // which worker
        for(int j = 1; j <= n; j++) { // which time
            int p = (i - 1) * n + j;
            for(int k = 1; k <= n; k++) { // which car
                addedge(m * n + k, p, 1, j * t[k][i]);
            }
            addedge(p, T, 1, 0);
        }
    }
    mcmf(S, T);
    printf("%.2lf", cost / double(n));
    return 0;
}