今天是弟弟的 10 岁生日，祝他以后不要成为一个臭学信息的。
Cindy，玩原玩的。我忘了叫什么什么酩，不玩原导致的。
概念认知
所谓咕咕咕……
A. 草地排水
http://222.180.160.110:1024/contest/3696/problem/1
B. 完美的牛栏 The Perfect Stall
http://222.180.160.110:1024/contest/3696/problem/2
C. 奶牛食品
http://222.180.160.110:1024/contest/3696/problem/3
A. 小行星
http://222.180.160.110:1024/contest/3821/problem/1
一次可以选择清一行或一列。
我们对于每个小行星 \((x, y)\)，将第 \(x\) 行和第 \(y\) 列连边，则每行发出的边可只要选择该行即可清楚，每列同理。
故原问题转化为二分图的最小点覆盖，即最大匹配。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int inf = 1e18;
const int maxn = 2e3 + 5;
const int maxm = 3e4 + 5;
int tag, gs, gt;
int n, m, x, y, w, tot = 1;
int vis[maxn], now[maxn], dep[maxn];
int h[maxn], to[maxm], ne[maxm], tw[maxm];
inline int min(int x, int y) {
return x < y ? x : y;
}
bool BFS(void) {
std::fill(dep + 1, dep + n + 1, 0);
std::queue<int> q;
dep[gs] = 1, vis[gs] = tag;
q.push(gs), now[gs] = h[gs];
while (!q.empty()) {
int f = q.front();
q.pop();
for (int i = h[f]; i; i = ne[i]) {
int v = to[i], w = tw[i];
if (vis[v] == tag || w == 0)
continue;
vis[v] = tag, 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 = ne[i]) {
int v = to[i], w = tw[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;
tw[i] -= t, tw[i ^ 1] += t;
}
now[x] = i;
return flow - rest;
}
inline int Dinic(void) {
int res = 0;
for (tag = 1; BFS(); ++tag) {
int t = findP(gs);
while (t) {
res += t;
t = findP(gs);
}
}
return res;
}
inline void add(int x, int y, int w) {
to[++tot] = y, tw[tot] = w;
ne[tot] = h[x], h[x] = tot;
return;
}
int main() {
read(n), read(m);
gs = 2 * n + 1, gt = gs + 1;
for (int i = 1; i <= n; ++i)
add(gs, i, 1), add(i, gs, 0);
for (int i = n + 1; i <= 2 * n; ++i)
add(i, gt, 1), add(gt, i, 0);
while (m--) {
read(x), read(y);
add(x, y + n, 1), add(y + n, x, 0);
}
print(Dinic(), '\n');
return 0;
}
} // namespace XSC062
#undef int
B. 秘密挤奶机
http://222.180.160.110:1024/contest/3821/problem/2
题目那么长，其实就是说要求找到从 1 到 N 的 \(T\) 条路径，每条边不能同时被两条路径包含。
显然题目具有单调性。我们二分最大边权，只添加边权小于等于 mid 的边并令双向剩余量为 1（这样每条边就只会被选一次），跑一遍 Dinic 即可得到答案。
不知道为什么如果把 vis 数组改成时间戳而非每次清空就过不了（我为什么会发现这种事情呢，哭哭）。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int inf = 1e18;
const int maxn = 2e3 + 5;
const int maxm = 8e4 + 5;
int gs, gt;
bool vis[maxn];
int n, m, t, tot;
int l, mid, r, res;
int now[maxn], dep[maxn];
int x[maxm], y[maxm], w[maxm];
int h[maxn], to[maxm], ne[maxm], tw[maxm];
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(void) {
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 = ne[i]) {
int v = to[i], w = tw[i];
if (vis[v]|| 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 = ne[i]) {
int v = to[i], w = tw[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;
tw[i] -= t, tw[i ^ 1] += t;
}
now[x] = i;
return flow - rest;
}
inline int Dinic(void) {
int res = 0;
for (; BFS();) {
int t = findP(gs);
while (t) {
res += t;
t = findP(gs);
}
}
return res;
}
inline void Init(void) {
tot = 1;
for (int i = 1; i <= n; ++i)
h[i] = 0;
return;
}
inline void add(int x, int y, int w) {
to[++tot] = y, tw[tot] = w;
ne[tot] = h[x], h[x] = tot;
return;
}
inline bool check(int p) {
Init();
for (int i = 1; i <= m; ++i) {
if (w[i] <= p) {
add(x[i], y[i], 1);
add(y[i], x[i], 1);
}
}
int u = Dinic();
return u >= t;
}
int main() {
read(n), read(m), read(t);
gs = 1, gt = n, l = inf, r = -inf;
for (int i = 1; i <= m; ++i) {
read(x[i]), read(y[i]), read(w[i]);
l = min(l, w[i]), r = max(r, w[i]);
}
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) {
r = mid - 1;
res = mid;
}
else l = mid + 1;
}
print(res, '\n');
return 0;
}
} // namespace XSC062
#undef int
C. 猪
http://222.180.160.110:1024/contest/3821/problem/3
因为改换猪的位置而带来的「继承」关系是问题的难点。
我们先按常规思路走，开大源点连每个猪圈，权值为猪圈内初始猪数；连猪圈和对应的人，权值为无穷大；开大汇点连每个人，权值为这个人要买的猪数。
一开始的思路是，对于每一个人，将他可以开门的猪圈进行两两之间连边，但这样时间复杂度会达到 \(\mathcal O(n\times m^2)\)。
所以我们转而考虑通过人之间的传递来进行「继承」操作。
对于一个人，若他能开某个门，将他和上一个能开这个门的人连边，这样继承关系就一条龙传下来了。
注意处理重边以防超时。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int inf = 1e18;
const int maxn = 2e3 + 5;
const int maxm = 8e4 + 5;
int gs, gt;
bool vis[maxn];
bool p[maxn][maxn];
int n, m, x, y, tot = 1;
int now[maxn], dep[maxn], la[maxn];
int h[maxn], to[maxm], ne[maxm], tw[maxm];
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 = ne[i]) {
int v = to[i], w = tw[i];
if (vis[v]|| 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 = ne[i]) {
int v = to[i], w = tw[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;
tw[i] -= t, tw[i ^ 1] += t;
}
now[x] = i;
return flow - rest;
}
inline int Dinic(int n) {
int res = 0;
for (; BFS(n);) {
int t = findP(gs);
while (t) {
res += t;
t = findP(gs);
}
}
return res;
}
inline void add(int x, int y, int w) {
to[++tot] = y, tw[tot] = w;
ne[tot] = h[x], h[x] = tot;
return;
}
int main() {
read(m), read(n);
gs = n + m + 1, gt = n + m + 2;
for (int i = 1; i <= m; ++i) {
read(x);
add(gs, i + n, x);
add(i + n, gs, 0);
}
for (int i = 1; i <= n; ++i) {
read(x);
while (x--) {
read(y), y += n;
if (la[y] && !p[i][la[y]]) {
p[i][la[y]] = 1;
p[la[y]][i] = 1;
add(la[y], i, inf);
add(i, la[y], 0);
}
add(y, i, inf), add(i, y, 0);
la[y] = i;
}
read(x);
add(i, gt, x), add(gt, i, 0);
}
print(Dinic(gt), '\n');
return 0;
}
} // namespace XSC062
#undef int