题目链接:POJ3020-Antenna Placement
题意:
给一个网格图,图上有一些特殊点,要求建信号塔,一个信号塔最多只能覆盖相邻的两个特殊点,问最少需要多少信号塔。
题解:
最小路径覆盖。
对于每个特殊点编号,然后相邻的互相建边,然后求最大匹配,因为是无向图,所以求出的最大匹配应该/2。
最小路径覆盖=总点数-最大匹配。
参考代码:
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 409;
const int MAXM = 409 * 409;
int T, n, m, tot;
int nxt[5][5], mp[50][50], match[MAXN];
bool used[MAXN];
struct EDGE
{
int v, nxt;
} edge[MAXM];
int fir[MAXN], cnt = 0;
void addedge(int u, int v)
{
edge[cnt].v = v;
edge[cnt].nxt = fir[u];
fir[u] = cnt++;
}
bool dfs(int u)
{
for (int i = fir[u]; i != -1; i = edge[i].nxt)
{
int v = edge[i].v;
if (!used[v])
{
used[v] = 1;
if (match[v] == -1 || dfs(match[v]))
{
match[v] = u;
return 1;
}
}
}
return 0;
}
int MaxMatch()
{
int sum = 0;
memset(match, -1, sizeof(match));
for (int i = 1; i <= tot; i++)
{
memset(used, 0, sizeof(used));
if (dfs(i))
sum++;
}
return sum;
}
int main()
{
cin >> T;
nxt[1][1] = 1;
nxt[2][1] = -1;
nxt[3][1] = 0;
nxt[4][1] = 0;
nxt[1][2] = 0;
nxt[2][2] = 0;
nxt[3][2] = 1;
nxt[4][2] = -1;
while (T--)
{
cin >> n >> m;
memset(fir, -1, sizeof(fir));
tot = cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
char c;
cin >> c;
if (c != '*')
mp[i][j] = 0;
else
mp[i][j] = ++tot;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (mp[i][j])
for (int k = 1; k <= 4; k++)
{
int tx = i + nxt[k][1];
int ty = j + nxt[k][2];
if (!mp[tx][ty] || tx < 1 || tx > n || ty < 1 || ty > m)
continue;
addedge(mp[i][j], mp[tx][ty]);
}
int ans = MaxMatch();
cout << tot - ans / 2 << "\n";
}
return 0;
}