题目大意：给定一地图，*可以和相邻的*匹配成一对儿，问最少需要对儿匹配才能使所有*都被匹配到。
很直白的最小点覆盖，即ans = 点集数-最大匹配数。
不过一开始要对图进行遍历得到点集，找到一个*就把点集数+1，并和周围的匹配即可。为了防止重复，
我只匹配了左边和上边的点。由于用邻接表保存了双向路，所以最后匹配结果会是最大匹配的二倍。
数据范围是40*10，匈牙利即可，因此不用Karp进行优化。
附AC代码：
#include <stdio.h> #include <algorithm> #include <string.h> using namespace std; #define oo 0x3f3f3f3f char maps[50][20]; int nums[50][20]; struct ad { int next, to; } edge[1000000]; int head[1100], edge_num, used[1100], vis[1100]; void Add(int x, int y) { edge[edge_num].next = head[x]; edge[edge_num].to = y; head[x] = edge_num++; } bool Hungary(int u) { for(int i=head[u]; i!=-1; i=edge[i].next) { int To = edge[i].to; if(!vis[To]) { vis[To] = 1; if(!used[To] || Hungary(used[To])) { used[To] = u; return true; } } } return false; } int main() { int T; scanf("%d", &T); while(T--) { int m, n; scanf("%d %d", &m, &n); for(int i=0; i<m; i++) scanf("%s", maps[i]); int cnt = 0; memset(head, -1, sizeof(head)); edge_num = 0; for(int i=0; i<m; i++) for(int j=0; j<n; j++) { if(maps[i][j]=='*') { cnt++; nums[i][j] = cnt; if(i>=1 && maps[i-1][j]=='*') { Add(nums[i-1][j], nums[i][j]); Add(nums[i][j], nums[i-1][j]); } if(j>=1 && maps[i][j-1]=='*') { Add(nums[i][j], nums[i][j-1]); Add(nums[i][j-1], nums[i][j]); } } } memset(used, 0, sizeof(used)); int ans = 0; for(int i=1; i<=cnt; i++) { memset(vis, 0, sizeof(vis)); if(Hungary(i))ans++; } printf("%d ", cnt-ans/2); } return 0; }
Karp算法优化代码：
#include <stdio.h> #include <algorithm> #include <string.h> #include <queue> using namespace std; #define oo 0x3f3f3f3f const int Maxn = 1000; char maps[50][20]; int nums[50][20], head[Maxn]; struct ad { int to, next; }edge[Maxn*Maxn]; int depth, depx[Maxn], depy[Maxn], vis[Maxn], usedx[Maxn], usedy[Maxn], edge_num; void Add(int x, int y) { edge[edge_num].to = y; edge[edge_num].next = head[x]; head[x] = edge_num++; } bool bfs(int cnt) { memset(depx, -1, sizeof(depx)); memset(depy, -1, sizeof(depy)); depth = oo; queue<int>Q; for(int i=1; i<=cnt; i++) { if(!usedx[i]) { depx[i] = 0; Q.push(i); } } while(Q.size()) { int now = Q.front(); Q.pop(); if(depx[now]>depth)return true; for(int i=head[now]; i!=-1; i=edge[i].next) { int To = edge[i].to; if(depy[To] == -1) { depy[To] = depx[now] + 1; if(!usedy[To]) depth = depy[To]; else { depx[usedy[To]] = depy[To] + 1; Q.push(usedy[To]); } } } } if(depth==oo)return false; return true; } bool Hungary(int u) { for(int i=head[u]; i!=-1; i=edge[i].next) { int To = edge[i].to; if(!vis[To]) { vis[To] = 1; if(usedy[To] && depy[To]==depth)continue; if(!usedy[To] || Hungary(usedy[To])) { usedx[u] = To; usedy[To] = u; return true; } } } return false; } int Karp(int cnt) { memset(usedx, 0, sizeof(usedx)); memset(usedy, 0, sizeof(usedy)); int ans = 0; while(bfs(cnt)) { memset(vis, 0, sizeof(vis)); for(int i=1; i<=cnt; i++) if(!usedx[i] && Hungary(i))ans++; } return ans; } int main() { int T; scanf("%d", &T); while(T--) { int n, m; edge_num = 0; scanf("%d %d", &n, &m); for(int i=0; i<n; i++) scanf("%s", maps[i]); memset(head, -1, sizeof(head)); int cnt = 0; for(int i=0; i<n; i++) for(int j=0; j<m; j++) { if(maps[i][j]=='*') { cnt++; nums[i][j] = cnt; if(i-1>=0 && maps[i-1][j]=='*') { Add(nums[i-1][j], nums[i][j]); Add(nums[i][j], nums[i-1][j]); } if(j-1>=0 && maps[i][j-1]=='*') { Add(nums[i][j], nums[i][j-1]); Add(nums[i][j-1], nums[i][j]); } } } int ans = Karp(cnt); printf("%d ", cnt-ans/2); } return 0; }