黑暗爆炸 2696. 航班安排

发表于 分类于

链接

https://darkbzoj.tk/problem/2696

题意

神犇航空有 $K$ 架飞机，$N$ 个机场，以 $0\sim N−1$ 编号，其中 $0$ 号为基地机场，每天 $0$ 时刻起飞机才可以从该机场起飞，并不晚于 $T$ 时刻回到该机场

现在有 $M$ 个包机请求，每个请求为在 $s$ 时刻从 $a$ 机场起飞，在恰好 $t$ 时刻到达 $b$ 机场，可以净获利 $c$

设计一种方案，使得总收益最大

$t_{ij}$ 表示从机场 $i$ 空载飞至机场 $j$，需要时间 $t_{ij}$

$f_{ij}$ 表示从机场 $i$ 空载飞至机场 $j$，需要费用 $f_{ij}$

思路

将每个请求拆成两个点 $u,v$ 连边，容量为 $1$，费用为 $-c$

如果在 $s$ 时刻能从基地飞到 $a$ 机场，则将基地与 $u$ 相连，容量为 $1$，费用为 $f[0][a]$

如果在 $t$ 时刻能从 $b$ 机场飞回基地，则将基地与汇点相连，容量为 $1$，费用为 $f[b][0]$

另外执行请求的飞机不一定是从基地飞过来的，所有枚举所有请求，判断飞完一个请求之后能不能飞到另一个请求的起点机场，如果可以，连边

最后将源点与基地相连，容量为 $k$，费用为 $0$

建完图后跑最小费用最短路即可，最小费用的相反数就是最大收益

代码

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
#include<bits/stdc++.h>
using namespace std;
const int N=500;
const int INF=0x3f3f3f3f;
int n,m,s,t,dist[N],cur[N],cost,a[N][N],b[N][N],o,p;
bool st[N];
vector<int> G[N];
struct E {
    int v,c,w;
    E(){}
    E(int v,int c,int w):v(v),c(c),w(w){}
};
struct Q {
    int u,v,s,t,c;
}c[N];
vector<E> e;
void addedge(int u,int v,int c,int w) {
    e.push_back(E(v,c,w));
    e.push_back(E(u,0,-w));
    G[u].push_back(e.size()-2);
    G[v].push_back(e.size()-1);
}
bool spfa() {
    for(int i=1;i<=n;i++) dist[i]=INF,st[i]=false;
    queue<int> q;
    q.push(s);
    dist[s]=0;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        st[u]=false;
        for(auto x:G[u]) {
            int &v=e[x].v,&c=e[x].c,&w=e[x].w;
            if(c>0&&dist[v]>dist[u]+w) {
                dist[v]=dist[u]+w;
                if(!st[v]) q.push(v),st[v]=true;
            }
        }
    }
    return dist[t]!=INF;
}
int dfs(int u,int a) {
    if(u==t) return a;
    int f,flow=0;
    st[u]=true;
    for(int &i=cur[u];i<G[u].size();i++) {
        int &v=e[G[u][i]].v,&c=e[G[u][i]].c,&w=e[G[u][i]].w;
        if(st[v]||c<=0||dist[v]!=dist[u]+w||(f=dfs(v,min(a,c)))<=0) continue;
        c-=f;
        e[G[u][i]^1].c+=f;
        a-=f;
        flow+=f;
        cost+=f*w;
        if(a==0) break;
    }
    st[u]=false;
    return flow;
}
int dinic() {
    int flow=0;
    while(spfa()) {
        for(int i=1;i<=n;i++) cur[i]=0;
        flow+=dfs(s,INF);
    }
    return flow;
}
int main() {
    scanf("%d%d%d%d",&n,&m,&o,&p);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&b[i][j]);
    s=m*2+1,t=m*2+3;
    addedge(s+1,s,o,0);
    for(int i=1;i<=m;i++) {
        scanf("%d%d%d%d%d",&c[i].u,&c[i].v,&c[i].s,&c[i].t,&c[i].c);
        c[i].u++,c[i].v++;
        addedge(i*2-1,i*2,1,-c[i].c);
        if(a[1][c[i].u]<=c[i].s) addedge(s,i*2-1,1,b[1][c[i].u]);
        if(a[c[i].v][1]+c[i].t<=p) addedge(i*2,t,1,b[c[i].v][1]);
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++) {
            if(i==j) continue;
            if(c[i].t+a[c[i].v][c[j].u]<=c[j].s) addedge(i*2,j*2-1,1,b[c[i].v][c[j].u]);
        }
    s++;
    n=t;
    dinic();
    printf("%d\n",-cost);
    return 0;
}