题目链接：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;
}