230722 做题记录 // 网络流 24 题 (3/24)
知耻而后勇，物极必反。
下文称「因为结点流量需要控制，故拆点」的操作为「保留节目」。
A. 星际转移问题
http://222.180.160.110:1024/contest/3952/problem/1
如果就按照题目给的路线图，我们显然无法考虑到飞船到达的时刻。同时 \(n\) 和 \(m\) 又很小，我们就知道了，「人不能两次踏进同一条河流」，1 时刻的站 \(p\) 和 2 时刻的站 \(p\) 也不能是同一个站 \(p\)。
考虑用 \((p, t)\) 表示 \(t\) 时刻的站 \(p\)，然后对于每条路线跑个暴力连边，容量全部为 \(H_i\)。
怎么控制时间最小呢？二分一下就可以了…… 然后最大流判定是不是满流的即可。由于空间站容量为无穷大，甚至没有保留节目 保留节目不再是保留节目了呜呜呜
以及注意到对于同一站点，前面的时刻可以留下来等后面的时刻，我们将同一站的前一时刻和后一时刻全部连边，容量为 \(k\)。以及保留节目对源点拆点以控制流量为 \(k\)。
经实验答案最大为 29，所以把二分上界设为 30 即可 理论上来说答案可能很大，比如你谷最后一组数据的答案就是 900 多，所以我掐指一算用天才般的算术技巧开了 \(10^4\)。真的，数数位天才就是我。
woc，这题居然没人做，果然我还是太强了
为什么都跑去做 T4 了，这个不是按难度顺序排列的吗
哦哦，好像不是，那（Na）没（Mei）事（Shi）了（Le）。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int lim = 1e4;
const int inf = 1e18;
const int maxm = 4e5 + 5;
const int maxn = 5e4 + 15;
struct _ {
int v, w, n;
_() {}
_(int v1, int w1, int n1) {
v = v1, w = w1, n = n1;
}
};
struct __ {
int c;
std::vector<int> p;
};
_ u[maxm];
__ w[maxn];
int h[maxn];
int l, mid, r;
int gs, gt, tot = 1;
int n, m, k, s, mt, x, res, y;
int vis[maxn], now[maxn], dep[maxn];
inline int fun(int p, int t) {
return (p - 1) * mt + t;
}
inline int min(int x, int y) {
return x < y ? x : y;
}
bool BFS(int n) {
std::fill(vis + 1, vis + n + 1, 0);
std::fill(dep + 1, dep + n + 1, 0);
std::queue<int> q;
dep[gs] = 1, vis[gs] = 1;
q.push(gs), now[gs] = h[gs];
while (!q.empty()) {
int f = q.front();
q.pop();
for (int i = h[f]; i; i = u[i].n) {
int v = u[i].v, w = u[i].w;
if (vis[v] == 1 || w == 0)
continue;
vis[v] = 1, now[v] = h[v];
dep[v] = dep[f] + 1, q.push(v);
if (v == gt)
return 1;
}
}
return 0;
}
int findP(int x, int flow = inf) {
if (x == gt)
return flow;
int rest = flow, i;
for (i = now[x]; rest && i; i = u[i].n) {
int v = u[i].v, w = u[i].w;
now[x] = i;
if (dep[v] != dep[x] + 1 || w == 0)
continue;
int t = findP(v, min(rest, w));
if (t == 0)
dep[v] = 0;
rest -= t;
u[i].w -= t, u[i ^ 1].w += t;
}
return flow - rest;
}
inline int Dinic(int n) {
int res = 0;
while (BFS(n)) {
int t = findP(gs);
while (t) {
res += t;
t = findP(gs);
}
}
return res;
}
inline void add(int x, int y, int w) {
u[++tot] = _(y, w, h[x]);
h[x] = tot;
return;
}
inline void addf(int x, int y, int w) {
add(x, y, w), add(y, x, 0);
return;
}
inline void Init(void) {
tot = 1;
memset(h, 0, sizeof (h));
return;
}
inline bool check(int x) {
Init();
mt = x, s = fun(n, mt) + 1;
gs = s + 1, gt = s + 2;
addf(gs, s, k);
for (int i = 1; i <= mt; ++i) {
addf(s, fun(n - 1, i), k);
addf(fun(n, i), gt, k);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < mt; ++j)
addf(fun(i, j), fun(i, j + 1), k);
}
for (int i = 1; i <= m; ++i) {
int p = 0, x = 0, la = 0;
while (++p <= mt) {
if (la != 0) {
addf(fun(la, p - 1),
fun(w[i].p[x], p), w[i].c);
}
la = w[i].p[x];
if (++x >= w[i].p.size())
x = 0;
}
}
return (Dinic(gt) == k);
}
int main() {
read(n), read(m), read(k);
for (int i = 1; i <= m; ++i) {
read(w[i].c), read(y);
while (y--) {
read(x);
if (x == 0)
x = n + 1;
else if (x == -1)
x = n + 2;
w[i].p.push_back(x);
}
}
n += 2;
l = 1, r = lim;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) {
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
print(res ? res - 1 : 0, '\n');
return 0;
}
} // namespace XSC062
#undef int
B. 最长递增子序列
http://222.180.160.110:1024/contest/3952/problem/2
就算知道不是按难度顺序排列我也要顺序开题。欸嘿，就是玩。
第一问很水，跑个 DP 就行。
第二问有点意思，取出就代表只能选一次，没想到这次保留节目这么前，总之把每个数拆成入点和出点，这样就可以只选一次了。
那怎么保证每次找到的流一定是 LIS 呢？其实这和我们 Dinic 的深度分层数组有异曲同工之妙，我们把 \(f_i = f_j + 1(i>j,A_i\ge A_j)\) 的 \((j, i)\) 连边，容量为 \(1\) 即可。
然后源点只和满足 \(f_x = 1\) 的 \(x\) 连边，相应地，汇点之和满足 \(f_x = \text{LIS}\) 的 \(x\) 连边。
第三问很好想啊，我们把 \(1\) 到源点和 \(n\) 到汇点的容量设成无穷大就好。
然后踩了半天的坑，这道题的保留节目部分不知道为什么必须要连双向边。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int inf = 1e18;
const int maxm = 4e5 + 5;
const int maxn = 5e5 + 15;
struct _ {
int v, w, n;
_() {}
_(int v1, int w1, int n1) {
v = v1, w = w1, n = n1;
}
};
_ u[maxm];
int n, res;
int gs, gt, tot = 1;
int a[maxn], h[maxn], f[maxn];
int vis[maxn], now[maxn], dep[maxn];
inline int min(int x, int y) {
return x < y ? x : y;
}
inline int max(int x, int y) {
return x > y ? x : y;
}
bool BFS(int n) {
std::fill(vis + 1, vis + n + 1, 0);
std::fill(dep + 1, dep + n + 1, 0);
std::queue<int> q;
dep[gs] = 1, vis[gs] = 1;
q.push(gs), now[gs] = h[gs];
while (!q.empty()) {
int f = q.front();
q.pop();
for (int i = h[f]; i; i = u[i].n) {
int v = u[i].v, w = u[i].w;
if (vis[v] == 1 || w == 0)
continue;
vis[v] = 1, now[v] = h[v];
dep[v] = dep[f] + 1, q.push(v);
if (v == gt)
return 1;
}
}
return 0;
}
int findP(int x, int flow = inf) {
if (x == gt)
return flow;
int rest = flow, i;
for (i = now[x]; rest && i; i = u[i].n) {
int v = u[i].v, w = u[i].w;
now[x] = i;
if (dep[v] != dep[x] + 1 || w == 0)
continue;
int t = findP(v, min(rest, w));
if (t == 0)
dep[v] = 0;
rest -= t;
u[i].w -= t, u[i ^ 1].w += t;
}
return flow - rest;
}
inline int Dinic(int n) {
int res = 0;
while (BFS(n)) {
int t = findP(gs);
while (t) {
res += t;
t = findP(gs);
}
}
return res;
}
inline void add(int x, int y, int w) {
u[++tot] = _(y, w, h[x]);
h[x] = tot;
return;
}
inline void addf(int x, int y, int w) {
add(x, y, w), add(y, x, 0);
return;
}
int main() {
read(n);
gs = 2 * n + 1, gt = gs + 1;
for (int i = 1; i <= n; ++i) {
read(a[i]);
f[i] = 1;
addf(i, i + n, 1);
addf(i + n, i, 1);
for (int j = 1; j < i; ++j) {
if (a[j] <= a[i])
f[i] = max(f[i], f[j] + 1);
}
res = max(res, f[i]);
for (int j = 1; j < i; ++j) {
if (a[j] <= a[i] &&
f[i] == f[j] + 1)
addf(j, i + n, 1);
}
}
for (int i = 1; i <= n; ++i) {
if (f[i] == 1)
addf(gs, i, 1);
if (f[i] == res)
addf(i + n, gt, 1);
}
print(res, '\n');
print(Dinic(gt), '\n');
tot = 1;
memset(h, 0, sizeof (h));
for (int i = 1; i <= n; ++i) {
addf(i, i + n, 1);
addf(i + n, i, 1);
for (int j = 1; j < i; ++j) {
if (a[j] <= a[i] &&
f[i] == f[j] + 1)
addf(j, i + n, 1);
}
}
for (int i = 1; i <= n; ++i) {
if (f[i] == 1) {
if (i == 1)
addf(gs, i, inf);
else addf(gs, i, 1);
}
if (f[i] == res) {
if (i == n)
addf(i + n, gt, inf);
else addf(i + n, gt, 1);
}
}
print(Dinic(gt), '\n');
return 0;
}
} // namespace XSC062
#undef int
C. 餐巾计划问题
http://222.180.160.110:1024/contest/3952/problem/3
这个有点简单啊。
—— · EOF · ——
真的什么也不剩啦 😖