原题地址
有一张m * n的地图，地图上有很多点，我们可以在某一点处建造一个区域，去包括这个点和它四周的的点中的其中一个（周围没有点仅包括这一个点也是可以的），问最小需要建造多少区域，可以将地图上所有的点全部包括
首先这个题目的条件是每一次建造一个区域，是只能包括住某一点和其四周的点中的其中一个，即最多包括两个点，那么我们要做的就是尽可能得去建造可以包括两个点的区域（即匹配问题），所以很容易得想到利用二分图匹配的算法，我们可以得到这个最值。再分析一下问题，最终我们需要得到包括所有的点的，且取最小的边数的匹配方案，那么就是二分图匹配中的最小路径覆盖问题，关于最小路径覆盖有一个定理：
最小路径覆盖 = 原图点数 - 二分图最大匹配数
那么我们通过记录每一个点，再遍历这些点，如果其四周存在点的话就将这个点和四周存在的点脸上边，这样我们就得到了一个有关系记录的邻接矩阵。 之后我们需要做的处理是，将这其中的每一个点拆成两个相同的点，一个放在集合A中，一个放在集合B中，然后由A出发对B做二分图最大匹配的匈牙利算法，值得注意的是，最后我们得到的最大匹配数需要除2才是原图的最大匹配数（因为拆成了两个点，关系也算了两次，匹配也是存在两个重复的情况） 最后我们就得到了答案。 代码：
//#include <bits/stdc++.h> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; const static int maxn = 400+10; int g[maxn][maxn]; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; int tok = 0; int ipmap[maxn][maxn]; int h, w; int uN, vN; int linker[maxn]; bool used[maxn]; void init() { memset(g, 0, sizeof(g)); memset(ipmap, 0, sizeof(ipmap)); tok = 0; scanf("%d %d", &h, &w); //printf("%d %d", h, w); for(int i=1; i<=h; i++) { for(int j=1; j<=w; j++) { char temp; cin>>temp; if(temp == '*') { ipmap[i][j] = ++tok; } } } for(int i=1; i<=h; i++) { for(int j=1; j<=w; j++) { if(ipmap[i][j]) { for(int k=0; k<4; k++) { int nx = i+dx[k]; int ny = j+dy[k]; if(nx < 1 || nx > h || ny < 1 || ny > w) continue; if(ipmap[nx][ny]) { g[ipmap[i][j]][ipmap[nx][ny]] = 1; g[ipmap[nx][ny]][ipmap[i][j]] = 1; } } } } } // for(int i=1; i<=tok; i++) // { // for(int j=1; j<=tok; j++) // printf("%d", g[i][j]); // printf("\n"); // } uN = vN = tok; } bool dfs(int u) { for(int v=1; v<=vN; v++) { if(g[u][v] && !used[v]) { used[v] = true; if(linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } } return false; } int hungary() { int res = 0; memset(linker, -1, sizeof(linker)); { for(int u=1; u<=uN; u++) { memset(used, false, sizeof(used)); if(dfs(u)) res++; } } return res; } int main() { int t; scanf("%d", &t); while(t--) { init(); printf("%d\n", tok - hungary()/2); } return 0; }小结一下 ： 当二分图的两个顶点子集基数相等时，该二分图所有顶点的匹配数 等于 任意一个顶点子集匹配数的2倍
