题解 P2711 【小行星】
Tweetuzki
2018-03-11 19:56:35
看到数据范围，以及“消除”、“最少次数”的字样，就知道与最小割有关。问题在于怎么割呢？
要消除一颗小行星，可以从三个面来消除。$x$ 面，$y$ 面和 $z$ 面。不难想到，将这三个面上的每一个坐标建两个点——入点和出点。由入点向出点连一条容量为 $1$ 的边。当入点和出点之间的这条边被割掉时，就说明是在这个面的这一个点消除了一次。
我们想要消除所有的小行星，就说明每一颗小行星在 $x$ 面，$y$ 面或 $z$ 面这三个面中，至少有一个面把它消除了。也就是说，不存在一条连通 $x-y-z$ 的路径，这就是割了。
于是我们对于每一颗小行星，从 $x$ 面的出点向 $y$ 面的入点连一条容量为 $INF$ 的边（仅为保证点之间的连通性），从 $y$ 面的出点向 $z$ 面的入点连容量为 $INF$ 的边。再从超级源向每个 $x$ 面的入点连容量为 $INF$ 的边，从每个 $z$ 面的出点向超级汇连容量为 $INF$ 的边。
建出来的图大致如下（样例）：
根据上面的分析，显然地，就是求 $s-t$ 最小割，这样就能保证每颗小行星都被消在某个面上。
但是……图好乱……
不难发现，这张图是可以简化的。注意到从超级源 $S$ 向每一个 $x$ 连出的边，下一条边都是从 $x$ 的入点向 $x$ 的出点连的一条容量为 $1$ 的边。根据 [Total Flow](https://www.luogu.org/problemnew/show/P2936) 一题可知，这两条边就类似于串联的关系，是可以合并的。
于是我们简化了这张图，改为直接从超级源 $S$ 向每个 $x$ （入点就可以不要了，于是就没有出入点之分了）连一条权值为 $1$ 的边。从 $z$ 面的边到终点同理，也可以简化。
简化后的图大致如下：
这样只要拆 $y$ 面的点就好了。是不是清爽多了？
最后求解该图的最小割即可。
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 500, INF = 0x7F7F7F7F;
struct edge {
int to, cap, rev;
};
int n, k;
vector <edge> G[MAXN*4+2];
edge make_edge(int to, int cap, int rev) {
edge x;
x.to = to, x.cap = cap, x.rev = rev;
return x;
}
void add_edge(int from, int to, int cap) {
G[from].push_back( make_edge(to, cap, G[to].size()) );
G[to].push_back( make_edge(from, 0, G[from].size() - 1) );
}
void init() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
add_edge(x, y + 500, INF);
add_edge(y + 500, y + 1000, 1);
add_edge(y + 1000, z + 1500, INF);
}
for (int i = 1; i <= 500; ++i) {
add_edge(0, i, 1);
add_edge(i + 1500, 2001, 1);
}
}
namespace Dinic {
int level[MAXN*4+2];
int iter[MAXN*4+2];
void bfs(int s) {
bool mark[MAXN*4+2];
queue <int> q;
memset(mark, 0, sizeof mark);
memset(level, -1, sizeof level);
q.push(s);
mark[s] = true;
level[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
mark[u] = false;
for (int i = 0; i < G[u].size(); ++i) {
edge &e = G[u][i];
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[u] + 1;
if (!mark[e.to]) {
mark[e.to] = true;
q.push(e.to);
}
}
}
}
}
int dfs(int u, int t, int f) {
if (u == t)
return f;
for (int &i = iter[u]; i < G[u].size(); ++i) {
edge &e = G[u][i];
if (e.cap > 0 && level[e.to] > level[u]) {
int d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
int max_flow(int s, int t) {
int flow = 0;
for (;;) {
bfs(s);
if (level[t] < 0)
return flow;
memset(iter, 0, sizeof iter);
int f;
while ( (f = dfs(s, t, INF)) > 0 )
flow += f;
}
}
}
int main() {
init();
printf("%d\n", Dinic::max_flow(0, 2001));
return 0;
}
```