Luogu – P4452 – [国家集训队]航班安排

题意

有 $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;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇