传送门：点击打开链接
题意：给你一个地图，里面有一些x，现在可以对着横排或者竖排开枪，可以把整排的x都打掉，问要清理完整个地图的x，至少需要多少次操作。
思路：最经典的一道最小点覆盖问题，把行和列分别当作点，如果(i,j)是x，那么就把行i和列j对应的点连一条边
看了别人的代码好像都是连单向边，然后直接只用了n个点，说实话有点没看懂，，我只会用2*n个节点，然后连双向边这样搞。。
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;const int MX = 1e4 + 5;
const int MS = 2e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;int Head[MX], erear;
struct Edge {int v, nxt;
} E[MS];
void edge_init() {erear = 0;memset(Head, -1, sizeof(Head));
}
void edge_add(int u, int v) {E[erear].v = v;E[erear].nxt = Head[u];Head[u] = erear++;
}int match[MX];
bool vis[MX];
bool DFS(int u) {for(int i = Head[u]; ~i; i = E[i].nxt) {int v = E[i].v;if(!vis[v]) {vis[v] = 1;if(match[v] == -1 || DFS(match[v])) {match[v] = u;return 1;}}}return 0;
}
int BM(int n) {int res = 0;memset(match, -1, sizeof(match));for(int u = 1; u <= n; u++) {memset(vis, 0, sizeof(vis));if(DFS(u)) res++;}return res;
}int main() {int n, m; //FIN;while(~scanf("%d%d", &n, &m)) {edge_init();for(int i = 1; i <= m; i++) {int x, y;scanf("%d%d", &x, &y);edge_add(x, y + n);edge_add(y + n, x);}printf("%d\n", BM(n));}return 0;
}