[JSOI2016]飞机调度

题目描述

思路

这道题目还是挺板的一道网络流，~~可是不知道为什么 LOJ 上的标签是最短路~~。

首先 最少需要多少架飞机 可以转化为 每架飞机尽量用更多的次数。

所以问题转化为一架飞机能够先飞路线 $i$ ，再飞路线 $j$ 的条件。

定义 $G_{i,j}$ 表示机场 $i$ 到机场 $j$ 并且在机场 $j$ 维修完毕的最短路径长度。

然而这个条件是显然的，需要满足从 $X_i$ 起飞到 $Y_i$ 再在 $Y_i$ 修理 $P_{Y_i}$ 的时间最后再走 $Y_i$ 到 $X_j$ 的最短路 的总时间要早于 $D_j$ ，这样两个机场就是可以由一架飞机走的，形式化的就是如下不等式：

D_i + T_{X_i,Y_i} + P_{Y_i} + G_{Y_i, X_j} \le D_j

对于每一个航线我们将其拆分成左航线和右航线，然后我们可以开始建一张二分图。

将所有左航线和源点连接，容量为 $1$ ；
将所有右航线和汇点连接，容量为 $1$ ；
假设一架飞机可以飞路线 $i$ 和路线 $j$ ，那么可以将 $i$ 对应的左航线和 $j$ 对应的右航线连接，容量为 $\infty$ 。

现在我们使用最少的飞机来飞这几条航线就相当于使用最少的路径来覆盖这一张二分图。

结论：答案为 $M-\text{二分图最大匹配} = M - \text{Max Flow}$ 。

简证：

这是一个经典模型：最小路径覆盖。

首先，每选择一条边相当于合并两个路径，那么我们需要尽可能的多选边，选的边数最多为二分图最大匹配。那么如果不合并的话每一个航线都需要自己独立跑，那么答案为 $M$ ，所以现在的答案为 $M-\text{二分图最大匹配} = M - \text{Max Flow}$ 。

代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500010;

struct _ {
    int To, Next, Value;
} G[MAXN << 1];
int Head[MAXN], Cnt = 1;

void _add(int u, int v, int w) {
    G[++Cnt] = {v, Head[u], w};
    Head[u] = Cnt;
}

void Add(int u, int v, int w) {
    _add(u, v, w);
    _add(v, u, 0);
}

int Depth[MAXN], Hash[MAXN], N, M, S, T;

void BFS() {
    memset(Depth, -1, sizeof Depth);
    memset(Hash, 0, sizeof Hash);
    queue<int> q;
    q.push(T);
    Depth[T] = 0;
    Hash[0]++;

    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = Head[u]; i; i = G[i].Next) {
            int v = G[i].To;
            if (Depth[v] != -1) continue;
            Depth[v] = Depth[u] + 1;
            Hash[Depth[v]]++;
            q.push(v);
        }
    }
}

int Max_Flow;

int DFS(int u, int flow) {
    if (u == T) {
        Max_Flow += flow;
        return flow;
    }
    int used = 0;
    for (int i = Head[u]; i; i = G[i].Next) {
        int v = G[i].To;
        if (G[i].Value && Depth[v] + 1 == Depth[u]) {
            int Min = DFS(v, min(G[i].Value, flow - used));
            if (Min) {
                G[i].Value -= Min;
                G[i ^ 1].Value += Min;
                used += Min;
            }
            if (used == flow) {
                return used;
            }
        }
    }

    Hash[Depth[u]]--;
    if (Hash[Depth[u]] == 0) Depth[S] = MAXN - 5;
    Depth[u]++;
    Hash[Depth[u]]++;
    return used;
}

int ISAP() {
    Max_Flow = 0;
    BFS();
    while (Depth[S] < MAXN - 5) DFS(S, 0x3f3f3f3f);
    return Max_Flow;
}

int Graph[510][510], X[510], Y[510], D[510], P[510], Cost[510][510];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    S = M * 2 + 1, T = M * 2 + 2;

    for (int i = 1; i <= N; i++) {
        cin >> P[i];
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> Graph[i][j];
            Cost[i][j] = Graph[i][j];
        }
    }

    for (int i = 1; i <= M; i++) {
        cin >> X[i] >> Y[i] >> D[i];
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i == j) continue;
            Graph[i][j] = Cost[i][j] + P[j];
        }
    }

    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                Graph[i][j] = min(Graph[i][j], Graph[i][k] + Graph[k][j]);
            }
        }
    }

    for (int i = 1; i <= M; i++) {
        Add(S, i, 1);
    }
    for (int i = 1; i <= M; i++) {
        Add(i + M, T, 1);
    }
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= M; j++) {
            if (D[i] + Cost[X[i]][Y[i]] + P[Y[i]] + Graph[Y[i]][X[j]] <= D[j]) {
                Add(i, j + M, 0x3f3f3f3f);
            }
        }
    }

    cout << M - ISAP() << endl;
    return 0;
}