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

发表于 | 阅读数

可以有$k$架飞机，$0..N-1$个机场，神犇航空接到了$M$个包机请求，每个请求为在$s$时刻从$a$机场起飞，在恰好$t$时刻到达$b$机场，可以净获利$c$。有机场之间来往的费用与时间

注意！是净获利。（不然样例都想不通)

考虑以飞机为流量，请求为点。由于一个请求只能一次，考虑拆点。如果请求之间不相交，表示可以停留一会然后完成下一个请求

  • 每个请求完成后与$t$连上可以返回的边。
  • 如果有时间进行下一个请求连上费用的边。
  • 所有可行建立在从从$0$号机场连边。
  • 如果无法在时间内完成请求就跑路。
  • $t_{ij} <=t_{ik}+t_{kj},f_{ij}<=f_{ik}+f_{kj}$满足最短路，这样上面那个情况就不会发生，完成下一个请求就会好回去。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
#define INF 0x3f3f3f3f
const int N = 200 + 10;
const int mod = 1e9 + 7;
int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + c - '0', c = getchar();
return x \* f;
}
struct Edge
{
int to, cap, nxt, f;
Edge() {}
Edge(int v, int c, int t, int k) : to(v), cap(c), nxt(t), f(k) {}
};
const int EN = 5e3 + 10;
const int EM = 5e4 + 10;
struct MCMF
{

    Edge e[EM << 1];
    int head[EN], scnt;
    int f[EN], dis[EN], vis[EN];
    pii pre[EN];
    MCMF() { scnt = 1; }
    void addEdge(int u, int v, int w, int k)
    {

        e[++scnt] = Edge(v, w, head[u], k);
        head[u] = scnt;
        e[++scnt] = Edge(u, 0, head[v], -k); ///!!!!
        head[v] = scnt;
    }
    bool spfa(int s, int t)
    {
        memset(vis, 0, sizeof(vis));
        memset(dis, INF, sizeof(dis));
        queue<int> q;
        dis[s] = 0;
        vis[s] = 1;
        f[s] = INF;
        q.push(s);
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            vis[x] = 0;
            for (int i = head[x]; i; i = e[i].nxt)
            {
                int to = e[i].to;

                if (dis[to] > dis[x] + e[i].f && e[i].cap)
                {
                    pre[to] = mk(x, i);
                    dis[to] = dis[x] + e[i].f;
                    f[to] = min(f[x], e[i].cap);
                    if (!vis[to])
                    {
                        vis[to] = 1;
                        q.push(to);
                    }
                }
            }
        }
        return dis[t] != INF;
    }
    pii Maxflow(int s, int t)
    {
        int flow = 0, res = 0;
        while (spfa(s, t))
        {

            for (int u = t; u != s; u = pre[u].first)
            {
                e[pre[u].second].cap -= f[t];
                e[pre[u].second ^ 1].cap += f[t];
                res += e[pre[u].second].f * f[t];
            }
            flow += f[t];
        }
        return mk(flow, res);
    }

} mc;
struct node
{
int a, b, s, t, c;
} p[N];
int ti[N][n], f[N][n];
int main()
{
int n = read(), m = read(), k = read(), T = read();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
ti[i][j] = read();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
f[i][j] = read();
for (int i = 1; i <= m; i++)
p[i].a = read(), p[i].b = read(), p[i].s = read(), p[i].t = read(), p[i].c = read();
int cnt = 2 \* m;
int s = ++cnt, q = ++cnt, t = ++cnt;
mc.addEdge(s, q, k, 0);
for (int i = 1; i <= m; i++)
{
mc.addEdge(i, i + m, 1, -p[i].c);
if (p[i].t + ti[p[i].b][0] > T)
continue;
if (p[i].s >= ti[0]p[i].a])
mc.addEdge(q, i, INF, f[0]p[i].a]);
mc.addEdge(i + m, t, INF, f[p[i].b][0]);
for (int j = 1; j <= m; j++)
if (p[i].t + ti[p[i].b][p[j].a] <= p[j].s)
mc.addEdge(i + m, j, INF, f[p[i].b][p[j].a]);
}

    printf("%d\n", -mc.Maxflow(s, t).second);

}

</details>
```