消除格子 / Asteroids G

题目链接：ybt金牌导航3-1-1 / POJ 3041 / luogu P7368

题目大意

有 n*n 的矩阵，然后有一些格子上可能会有杂物。
每次打扫可以选一行或者一列，把那一行或者那一列的所有杂物消掉。
问你最小消除次数使得所有杂物都被消掉。

思路

首先，你想着用网络流搞搞这道题。

接着，你会发现把一行的杂物都消掉，就是可以把横纵坐标分别看成两边的点，然后如果 $(x,y)$ 有杂物，那就让左边的 $x$ 点连向右边的 $y$ 点。
然后就构成了二分图，那你要所有杂物都被弄到，那你可以这样想，他就是要最小点覆盖：找尽可能少的点，使得所有边连接的点至少有一个是你选中的。

那这个最小点覆盖就是最大流，那 dinic 搞就完事了。

代码

#include<queue>
#include<cstdio>
#include<cstring>

using namespace std;

struct node {
	int x, to, nxt, op;
}e[400001];
int n, k, le[2001], KK;
int x, y, s, t, ans;
int dis[2001];

void add(int x, int y, int z) {
	e[++KK] = (node){z, y, le[x], KK + 1}; le[x] = KK;
	e[++KK] = (node){0, x, le[y], KK - 1}; le[y] = KK;
}

bool bfs() {
	memset(dis, 0x7f, sizeof(dis));
	queue <int> q;
	
	q.push(s);
	dis[s] = 0;
	if (s == t) return 1;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		
		for (int i = le[now]; i; i = e[i].nxt)
			if (e[i].x && dis[e[i].to] > dis[now] + 1) {
				dis[e[i].to] = dis[now] + 1;
				if (e[i].to == t) return 1;
				q.push(e[i].to);
			}
	}
	
	return 0;
}

int dfs(int now, int maxn) {
	if (now == t) return maxn;
	
	int now_go = 0;
	
	for (int i = le[now]; i; i = e[i].nxt)
		if (dis[e[i].to] == dis[now] + 1 && e[i].x) {
			int this_go = dfs(e[i].to, min(maxn - now_go, e[i].x));
			e[i].x -= this_go;
			e[e[i].op].x += this_go;
			now_go += this_go;
			if (now_go == maxn) return now_go;
		}
	
	return now_go;
}

void dinic() {
	while (bfs())
		ans += dfs(s, 2147483647);
}

int main() {
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= k; i++) {//建图
		scanf("%d %d", &x, &y);
		add(x, n + y, 2147483647);
	}
	
	s = 2 * n + 1;
	t = 2 * n + 2;
	for (int i = 1; i <= n; i++) {//连跟源点汇点连的边
		add(s, i, 1);
		add(n + i, t, 1);
	}
	
	dinic();
	
	printf("%d", ans);
	
	return 0;
}