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