【洛谷-P4452】[国家集训队]航班安排 • TonyYin's Blog

题意#

有 $K$ 架飞机， $N$ 个机场，其中 $1$ 号为基地机场。

每天 $0$ 时刻，飞机才可以从基地机场起飞，并且不晚于 $T$ 时刻回到基地机场。

对于 $\forall i, j$ ，题目给定 $t_{i, j}$ 表示从 $i$ 空载飞到 $j$ 需要的时间， $f_{i, j}$ 表示从 $i$ 空载飞到 $j$ 需要的费用。

有 $M$ 个包机请求，给定 $(a, b, s, t, c)$ ，表示在 $s$ 时刻从 $a$ 机场起飞，可以恰好在 $t$ 时刻到达 $b$ 机场，净获利 $c$ .

注意，包机请求的飞行时间为 $(t-s)\neq t_{a, b}$ . 包机请求的费用为 $-c$ ，与 $f$ 不同。

求最大总收益。

分析#

不难发现，可以使用费用流算法。

对请求进行拆点。起点向终点连容量为 $1$ ，价值为 $c$ 的边。

然后处理时间限制。对于每个请求，如果：

**可以在请求开始之前，从基地飞到起点：**从源点向请求起点连边，容量为 $\inf$ ，价值为对应的 $-f$ .
**可以在 $T$ 之前，从终点飞到基地：**从终点向汇点连边，容量为 $\inf$ ，价值为对应的 $-f$ .

又因为执行请求之后，可以飞到别的请求机场。所以两两枚举请求，如果从终点飞到另一个请求的起点满足时间条件，就连边。

处理 $k$ 架飞机。再建立一个源点，向原来的源点连容量为 $k$ ，费用为 $0$ 的边即可。

跑最大费用最大流。

代码#

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 408, MAXM = 1e6;
const int inf = 0x3f3f3f3f;
int n, m, k, ed;
int Tim[MAXN][MAXN], Cos[MAXN][MAXN];
int S, T;
struct Edge{
    int from, to, nxt, flow, val;
}edge[MAXM];
int head[MAXN], e_cnt = 1;
void add(int u, int v, int w, int c) {
    edge[++e_cnt].from = u;
    edge[e_cnt].to = v;
    edge[e_cnt].flow = w;
    edge[e_cnt].val = c;
    edge[e_cnt].nxt = head[u];
    head[u] = e_cnt;
}
void add_edge(int u, int v, int w, int c) {
    add(u, v, w, c);
    add(v, u, 0, -c);
}
struct In{int a, b, s, t, c;} in[MAXN];
int dis[MAXN], pre[MAXN];
bool vis[MAXN];
bool SPFA() {
    memset(dis, 0x3f, sizeof(dis)); dis[S] = 0;
    memset(vis, 0, sizeof(vis)); vis[S] = true;
    memset(pre, 0, sizeof(pre));
    queue<int> q; q.push(S);
    while(!q.empty()) {
        int x = q.front(); q.pop(); vis[x] = false;
        for(int i = head[x]; i; i = edge[i].nxt) {
            int v = edge[i].to, flow = edge[i].flow, val = edge[i].val;
            if(flow && dis[x] + val < dis[v]) {
                dis[v] = dis[x] + val;
                pre[v] = i;
                if(!vis[v]) {
                    q.push(v); vis[v] = true;
                }
            }
        }
    }
    return (pre[T] != 0);
}
pair<int, int> MCMF() {
    int flow = 0, cost = 0;
    while(SPFA()) {
        int minflow = inf;
        for(int i = T; i != S; i = edge[pre[i]].from) {
            minflow = min(minflow, edge[pre[i]].flow);
        }
        flow += minflow;
        for(int i = T; i != S; i = edge[pre[i]].from) {
            edge[pre[i]].flow -= minflow;
            edge[pre[i] ^ 1].flow += minflow;
            cost += edge[pre[i]].val * minflow;
        }
    }
    return make_pair(flow, cost);
}
int main() {
    scanf("%d%d%d%d", &n, &m, &k, &ed);
    S = 0; T = 2 * m + 2;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            scanf("%d", &Tim[i][j]);
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            scanf("%d", &Cos[i][j]);
        }
    }
    add_edge(S, S + 1, k, 0);
    for(int i = 1; i <= m; i++) scanf("%d%d%d%d%d", &in[i].a, &in[i].b, &in[i].s, &in[i].t, &in[i].c);
    for(int i = 1; i <= m; i++) {
        add_edge(i + 1, i + m + 1, 1, -in[i].c);
        if(in[i].t + Tim[in[i].b + 1][1] <= ed) add_edge(i + m + 1, T, inf, Cos[in[i].b + 1][1]);
        if(in[i].s - Tim[1][in[i].a + 1] >= 0) add_edge(S + 1, i + 1, inf, Cos[1][in[i].a + 1]);
        for(int j = 1; j <= m; j++) {
            if(in[i].t + Tim[in[i].b + 1][in[j].a + 1] <= in[j].s) {
                add_edge(i + m + 1, j + 1, inf, Cos[in[i].b + 1][in[j].a + 1]);
            }
        }
    }
    cout << -MCMF().second << endl;
    return 0;
}