[BZOJ1070][SCOI2007]修车

试题描述

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

输入

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

输出

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

输入示例

2 2
3 2
1 4

输出示例

1.50

数据规模及约定

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

题解

最小费用最大流问题。先建 n 个点表示车主，在建 m×n 个点表示每一时刻的工程师（技术人员），因为最多可能是一个工程师修理所有的车，所以最多有 n 个时刻。

然后考虑总等待时间，设某工程师修理了 k 辆车，所用时间分别为 A₁, A₂, ... , A_k. 那么第 i 个人等待时间 Wait_i = ΣA_j (1 ≤ j ≤ i) 设 S_i = ΣWait_j (1 ≤ j ≤ i)，则 S_i = Σ(i - j + 1) · A_j (1 ≤ j ≤ i) 所以我们不需要知道每一位顾客所等待的具体时间，只需要利用前面那个公式统计总时间即可。

从每个表示车主的节点连一条容量为 1，费用为 k * T 的有向边到相应的 k 时刻的技术人员，这一部分总共连 mn² 条边；源点向每个表示车主的点连一条容量 1 费用 0 的有向边；从每一时刻的每个技术人员所代表的点向汇点连一条容量 1 费用 0 的有向边，跑一边最小费用最大流即可。注意平均数最后要除以 n。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <cstdlib>
using namespace std;
 
int read() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}
 
#define maxn 610
#define maxm 666010
#define oo 2147483647
#define LL long long
 
struct Edge { int from, to, flow, cost; } ;
struct ZKW {
    int n, m, s, t, head[maxn], next[maxm];
    LL ans, cost;
    Edge es[maxm];
    bool inq[maxn];
    int d[maxn];
    bool vis[maxn];
    void init() {
        m = 0; memset(head, -1, sizeof(head));
        return ;
    }
    void AddEdge(int a, int b, int c, int d) {
        es[m] = (Edge){ a, b, c, d }; next[m] = head[a]; head[a] = m++;
        es[m] = (Edge){ b, a, 0, -d }; next[m] = head[b]; head[b] = m++;
        return ;
    }
    bool BFS() {
        for(int i = 1; i <= n; i++) d[i] = oo;
        memset(inq, 0, sizeof(inq));
        d[t] = 0;
        deque <int> Q; Q.push_front(t); inq[t] = 1;
        while(!Q.empty()) {
            int u = Q.front(); Q.pop_front(); inq[u] = 0;
            for(int i = head[u]; i != -1; i = next[i]) {
                Edge& e = es[i^1];
                if(e.flow && d[e.from] > d[u] + e.cost) {
                    d[e.from] = d[u] + e.cost;
                    if(!inq[e.from]) {
                        inq[e.from] = 1;
                        if(Q.empty() || d[e.from] <= d[Q.front()]) Q.push_front(e.from);
                        else Q.push_back(e.from);
                    }
                }
            }
        }
        if(d[s] == oo) return 0;
        for(int i = 0; i < m; i++) es[i].cost += d[es[i].to] - d[es[i].from];
        cost += d[s];
        return 1;
    }
    int DFS(int u, int a) {
        if(u == t || !a){ ans += cost * a; return a; }
        vis[u] = 1;
        int flow = 0, f;
        for(int i = head[u]; i != -1; i = next[i]) {
            Edge& e = es[i];
            if(!vis[e.to] && e.flow && !e.cost && (f = DFS(e.to, min(a, e.flow)))) {
                flow += f; a -= f;
                e.flow -= f; es[i^1].flow += f;
                if(!a) return flow;
            }
        }
        return flow;
    }
    void MinCost() {
        s = n - 1; t = n;
        ans = cost = 0;
        while(BFS())
            do
                memset(vis, 0, sizeof(vis));
            while(DFS(s, oo));
        return ;
    }
} sol;
 
int main() {
    sol.init();
    int m = read(), n = read();
    sol.n = n + n * m + 2; int s = sol.n - 1, t = sol.n;
    for(int i = 1; i <= n; i++) sol.AddEdge(s, i, 1, 0);
    for(int car = 1; car <= n; car++)
        for(int eng = 1; eng <= m; eng++) {
            int tmp = read();
            for(int i = 0; i < n; i++) sol.AddEdge(car, n+m*i+eng, 1, tmp*(i+1));
        }
    for(int eng = 1; eng <= m; eng++)
        for(int i = 0; i < n; i++) sol.AddEdge(n+m*i+eng, t, 1, 0);
     
    sol.MinCost();
    printf("%.2lf
", sol.ans / (double)n);
     
    return 0;
}