yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P2754 星际转移问题

发表于 更新于 分类于

P2754 星际转移问题

题面

题目链接

解法

套路地拆点。$pt_{u,t}$表示节点$u$在时间为$t$时的状态。按照太空船在$t$时的位置连边，跑最大流判断是否可行。

一种方法为二分答案，但是每次需要重新建图；另一种则是直接枚举答案，每次只连新加入的边，并且可以在残余网络上继续跑$maxflow$。据说二分反而跑的比枚举慢一些。

$G(V,E)$中$|V|$和$|E|$的范围

令$n=n+2$，先计算最长可能的时间$T$。最坏的可能性是只有一艘太空船且容量为$1$，并且这艘太空船在$n$个点之间周转。此时最长时间$T \le k \times n \le 750$（很多题解都说是$500$，其实是错的，洛谷讨论区里有$hack$）。

每次枚举新的时间，最多增加$n$个点，所以点集大小$|V| \le n \times T \le 11250$，开到$2 \times 10^4$即可。

而在每次添加路径时，$pt{u,t-1}$连向$pt{u,t}$，并且每艘太空船增加一条边，考虑网络流建反边需要$\times 2$，则每次最多添加$(n + m) \times 2 \le 80$条边，所以边集大小$|E| \le T \times 80 \le 60000$，开$10^5$管够。

AC代码

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
/**
 * @file:           P2754.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P2754
*/
// #pragma GCC optimize ("O2")
// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")
// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp &x) {
    bool sign = false;
    char ch = getchar();
    long double tmp = 1;
    for (; !isdigit(ch); ch = getchar())
        sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar())
        x = x * 10 + (ch ^ 48);
    if (ch == '.')
        for (ch = getchar(); isdigit(ch); ch = getchar())
            tmp /= 10.0, x += tmp * (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar((x % 10) ^ 48);
}
const int MAXN = 2e4 + 10;
const int MAXM = 1e5 + 10;
const int MAXS = 800;
const int MAXT = 55;
const int INF = 0x3f3f3f3f3f3f3f3f;
struct Dinic {
    struct Edge {
        int v, flow;
    } edge[MAXM];
    int tot = 1, flow = 0;
    int head[MAXN], nxt[MAXM], lev[MAXN], cur[MAXN];
    void addedge(int u, int v, int flow) {
        edge[++tot] = {v, flow};
        nxt[tot] = head[u], head[u] = tot;
        edge[++tot] = {u, 0};
        nxt[tot] = head[v], head[v] = tot;
    }
    bool bfs(int s, int t) {
        memset(lev, -1, sizeof(lev));
        queue<int> que;
        que.push(s);
        lev[s] = 0;
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (int i = head[u]; i; i = nxt[i]) {
                int v = edge[i].v;
                if (edge[i].flow && lev[v] == -1) {
                    lev[v] = lev[u] + 1;
                    que.push(v);
                }
            }
        }
        return lev[t] != -1;
    }
    int augment(int u, int t, int mx) {
        if (u == t || mx == 0)
            return mx;
        int ret = 0;
        for (int &i = cur[u]; i; i = nxt[i]) {
            int v = edge[i].v;
            if (lev[v] != lev[u] + 1)
                continue;
            int tmp = augment(v, t, min(mx, edge[i].flow));
            mx -= tmp, ret += tmp;
            edge[i].flow -= tmp, edge[i ^ 1].flow += tmp;
            if (mx == 0)
                break;
        }
        return ret;
    }
    int maxflow(int s, int t) {
        while (bfs(s, t)) {
            memcpy(cur, head, sizeof(cur));
            flow += augment(s, t, INF);
        }
        return flow;
    }
};
int n, m, k, sx, tx, ss, tt, num;
int h[MAXT], r[MAXT], s[MAXT][MAXT], pt[MAXT][MAXS];
Dinic maxflow;
signed main() {
    read(n), read(m), read(k);
    sx = n + 1, tx = n + 2;
    ss = ++num, tt = ++num;
    for (int i = 1; i <= m; ++i) {
        read(h[i]), read(r[i]);
        for (int j = 0; j < r[i]; ++j) {
            read(s[i][j]);
            if (s[i][j] == 0)
                s[i][j] = sx;
            if (s[i][j] == -1)
                s[i][j] = tx;
        }
    }
    for (int w = 0; w <= 750; ++w) {
        for (int i = 1; i <= n + 2; ++i)
            pt[i][w] = ++num;
        maxflow.addedge(ss, pt[sx][w], INF);
        maxflow.addedge(pt[tx][w], tt, INF);
        for (int i = 1; w && i <= n + 2; ++i)
            maxflow.addedge(pt[i][w - 1], pt[i][w], INF);
        for (int i = 1; w && i <= m; ++i) {
            int u = s[i][(w - 1) % r[i]];
            int v = s[i][w % r[i]];
            maxflow.addedge(pt[u][w - 1], pt[v][w], h[i]);
        }
        if (maxflow.maxflow(ss, tt) >= k)
            return write(w), putchar('\n'), 0;
    }
    puts("0");
    return 0;
}