P9409 题解
船酱魔王
·
·
题解
题意回顾
求出初始时最多的玩偶总数。
$ 1 \le tn,tm \le 3 \times 10^4 $。
## 分析
可以理解为，这是一个分层图，有 $ t+1 $ 层，第 $ i $ 层的 $ u $ 和第 $ i+1 $ 层的 $ v $ 存在一条有向边当且仅当第 $ i $ 天的座位图 $ u,v $ 存在连边。这 $ t+1 $ 层中的每个结点**限流** $ 1 $ 个玩偶。
**限流**怎么实现：将这个点拆成 $ u_1,u_2 $，入边连向 $ u_1 $，$ u_2 $ 连出出边，$ u_1,u_2 $ 连一条有向边，边限流为 $ 1 $，这样就把点限流转化为边限流了。
考虑初始时，玩偶是由『老师』分发的，由『老师』结点 $ 0 $ 向所有 $ 1 $ 层结点连有向边；最后，统计玩偶的总数，可以由所有 $ t+1 $ 层结点向『统计』结点连有向边。
此时，转化为『老师』向『统计』通过图上的边**最多**能传输多少个玩偶，有些边有一些限流，这不就是一个**图的有源汇最大流问题**吗？使用 Dinic 算法解决。
## AC 代码
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int N = 5e5 + 5;
int t, n;
int m;
struct node {
int v;
int w;
};
int wei[N];
int cm = 0;
vector<node> g[N];
inline int Id(int x, int typ, int y) {
return (x * 2 + typ - 3) * n + y;
}
void add(int u, int v, int zx, int fx) {
g[u].push_back((node){v, cm});
wei[cm++] = zx;
g[v].push_back((node){u, cm});
wei[cm++] = fx;
}
int dep[N];
int cur[N];
bool bfs(int from, int to) {
memset(dep, 0, sizeof(dep));
dep[from] = 1;
queue<int> que;
que.push(from);
while(!que.empty()) {
int u = que.front();
que.pop();
for(int i = 0; i < g[u].size(); i++) {
int v = g[u][i].v;
int w = g[u][i].w;
if(dep[v] || !wei[w]) continue;
dep[v] = dep[u] + 1, que.push(v);
}
}
return dep[to];
}
int dfs(int u, int to, int lim) {
int down = 0;
if(u == to) return lim;
for(int i = cur[u]; i < g[u].size(); i++) {
cur[u] = i;
int v = g[u][i].v;
int w = g[u][i].w;
if(dep[v] != dep[u] + 1 || !wei[w]) continue;
int ls = dfs(v, to, min(wei[w], lim - down));
if(!ls) dep[v] = 0;
wei[w] -= ls, wei[w ^ 1] += ls, down += ls;
if(down == lim) break;
}
return down;
}
int Dinic(int from, int to) {
int res = 0;
while(bfs(from, to)) {
memset(cur, 0, sizeof(cur));
res += dfs(from, to, 1e9 + 5);
}
return res;
}
int main() {
cin >> t >> n;
for(int i = 1; i <= n; i++) add(0, i, 1, 0);
for(int dy = 1; dy <= t; dy++) {
cin >> m;
int u, v;
for(int i = 1; i <= m; i++) {
cin >> u >> v;
add(Id(dy, 1, u), Id(dy, 2, v), 88, 0);
add(Id(dy, 1, v), Id(dy, 2, u), 88, 0);
}
for(int i = 1; i <= n; i++) add(Id(dy, 2, i), Id(dy + 1, 1, i), 1, 0);
}
int gzh = Id(t + 1, 1, 1);
for(int i = 1; i <= n; i++) add(Id(t, 2, i), gzh, 1, 0);
cout << Dinic(0, gzh) << endl;
return 0;
}
```