「SCOI2007」修车 - 费用流

发表于 | 分类于

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

顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

链接

BZOJ 1070
CodeVS 2436

题解

为每辆车建立点，为每个技术人员的每一次修车建立点。

设第 个技术人员修第 辆车所用时间为 ，第 辆车的点为 ，第 个技术人员倒数第 次修车（此时有 个人在等待）的点为 （）。

从源点向每辆车连边，容量为 1，费用为 0；从每个 向每个 连边，容量为 1，费用为 ；从每个 向汇点连边，容量为 1，费用为 0。

代码

#include <cstdio>
#include <climits>
#include <algorithm>
#include <queue>

const int MAXN = 60;
const int MAXM = 9;
const int MAXT = 1000;

struct Node;
struct Edge;

struct Node {
    Edge *firstEdge, *inEdge;
    int flow, dist;
    bool inQueue;
} nodes[MAXN + MAXM * MAXN + 2];

struct Edge {
    Node *from, *to;
    int flow, capacity, cost;
    Edge *next, *reversedEdge;

    Edge(Node *from, Node *to, int capacity, int cost) : from(from), to(to), flow(0), capacity(capacity), cost(cost), next(from->firstEdge) {}
};

struct Dinic {
    bool bellmanford(Node *s, Node *t, int n, int &flow, int &cost) {
        for (int i = 0; i < n; i++) {
            nodes[i].inEdge = NULL;
            nodes[i].flow = 0;
            nodes[i].dist = INT_MAX;
            nodes[i].inQueue = false;
        }

        std::queue<Node *> q;
        q.push(s);

        s->flow = INT_MAX;
        s->dist = 0;

        while (!q.empty()) {
            Node *v = q.front();
            q.pop();
            v->inQueue = false;

            for (Edge *e = v->firstEdge; e; e = e->next) {
                if (e->flow < e->capacity && e->to->dist > v->dist + e->cost) {
                    e->to->dist = v->dist + e->cost;
                    e->to->inEdge = e;
                    e->to->flow = std::min(v->flow, e->capacity - e->flow);
                    if (!e->to->inQueue) {
                        e->to->inQueue = true;
                        q.push(e->to);
                    }
                }
            }
        }

        if (t->dist == INT_MAX) return false;

        for (Edge *e = t->inEdge; e; e = e->from->inEdge) {
            e->flow += t->flow;
            e->reversedEdge->flow -= t->flow;
        }

        flow += t->flow;
        cost += t->flow * t->dist;

        return true;
    }

    void operator()(int s, int t, int n, int &flow, int &cost) {
        flow = cost = 0;
        while (bellmanford(&nodes[s], &nodes[t], n, flow, cost));
    }
} edmondskarp;

inline void addEdge(int from, int to, int capacity, int cost) {
    nodes[from].firstEdge = new Edge(&nodes[from], &nodes[to], capacity, cost);
    nodes[to].firstEdge = new Edge(&nodes[to], &nodes[from], 0, -cost);

    nodes[from].firstEdge->reversedEdge = nodes[to].firstEdge, nodes[to].firstEdge->reversedEdge = nodes[from].firstEdge;
}

int n, m, time[MAXM][MAXN];

inline int hash(int j, int k) {
    return n + (j - 1) * n + k;
}

int main() {
    scanf("%d %d", &m, &n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &time[j][i]);
        }
    }

    const int s = 0, t = n + n * m + 1;
    //printf("s = %d, t = %d\n", s, t);

    for (int i = 1; i <= n; i++) {
        addEdge(s, i, 1, 0);
    }

    for (int j = 1; j <= m; j++) {
        for (int k = 1; k <= n; k++) {
            addEdge(hash(j, k), t, 1, 0);
            for (int i = 1; i <= n; i++) {
                //printf("%d -> %d\n", i, hash(j, k));
                addEdge(i, hash(j, k), 1, time[j - 1][i - 1] * k);
            }
        }
    }

    int flow, cost;
    edmondskarp(s, t, n + n * m + 2, flow, cost);

    printf("%.2lf\n", (double)cost / (double)n);

    return 0;
}

吐槽

又一次把 、 读入倒了 ……

又一次敲错 EK 模板 ……

hehe