POJ1422 Air Raid【二分图最小途径覆盖】

POJ1422 Air Raid【二分图最小路径覆盖】

题目链接：

http://poj.org/problem?id=1422

题目大意：

有N个地点和M条有向街道，现在要在点上放一些伞兵，伞兵可以沿着有向街道走，直到不能走为止。

每条边只能被一个伞兵走一次。问：至少放多少伞兵，能使伞兵可以走到图上所有的点。

思路：

很明显的最小路径覆盖问题。先转换为二分图，先将N个点每个点拆成两个点，左边是1~N个点，右

边也是1~N个点。将有向街道变为左边点指向右边点的边。

因为二分图最小路径覆盖 = 点数 - 二分图最大匹配数，则求出结果就是放的最少伞兵数。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN = 140;

bool Map[MAXN][MAXN],Mask[MAXN];
int NX,NY;
int cx[MAXN],cy[MAXN];

int FindPath(int u)
{
    for(int i = 1; i <= NY; ++i)
    {
        if(Map[u][i] && !Mask[i])
        {
            Mask[i] = 1;
            if(cy[i] == -1 || FindPath(cy[i]))
            {
                cy[i] = u;
                cx[u] = i;
                return 1;
            }
        }
    }
    return 0;
}

int MaxMatch()
{
    for(int i = 1; i <= NX; ++i)
        cx[i] = -1;
    for(int i = 1; i <= NY; ++i)
        cy[i] = -1;

    int res = 0;
    for(int i = 1; i <= NX; ++i)
    {
        if(cx[i] == -1)
        {
            for(int j = 1; j <= NY; ++j)
                Mask[j] = 0;
            res += FindPath(i);
        }
    }
    return res;
}

int main()
{
    int T,N,M,u,v;
    scanf("%d",&T);
    while(T--)
    {
        memset(Map,0,sizeof(Map));
        scanf("%d%d",&N,&M);
        for(int i = 1; i<= M; ++i)
        {
            scanf("%d%d",&u,&v);
            Map[u][v] = 1;
        }
        NX = NY = N;
        printf("%d\n",N-MaxMatch());
    }

    return 0;
}