J - Air Raid - hdu 1151（最小边覆盖）

题意：给一个有向无环图，求出来最少需要几个士兵可以遍历所有的边。

分析：有向无环图的最小边覆盖 = 点数 - 最大匹配数

为什么是这样的公式？？可以思考一下，如果这N个点之间没有边，是不是应该有N个士兵去查看，但是如果增加一条边就应该减去这条边，以此类推，公式就比较容易明白了。

********************************************************************

#include<stdio.h>

#include<string.h>

#include<queue>

using namespace std;

const int MAXN = 205;

const int oo = 1e9+7;

bool G[MAXN][MAXN], used[MAXN];

int My[MAXN], N;

bool Find(int i)

{

    for(int j=1; j<=N; j++)

    {

        if( G[i][j] && used[j] == false )

        {

            used[j] = true;

            if( !My[j] || Find(My[j]))

            {

                My[j] = i;

                return true;

            }

        }

    }

    return false;

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int i, M, u, v, ans=0;

        scanf("%d%d", &N, &M);

        memset(G, false, sizeof(G));

        memset(My, false, sizeof(My));

        for(i=1; i<=M; i++)

        {

            scanf("%d%d", &u, &v);

            G[u][v] = true;

        }

        for(i=1; i<=N; i++)

        {

            memset(used, false, sizeof(used));

            if( Find(i) == true )

                ans++;

        }

        printf("%d\n", N-ans);

    }

    return 0;

}