POJ 1422 Air Raid(DAG最小パスオーバーライド)

POJ 1422 Air Raid(DAG最小パスオーバーライド)
http://poj.org/problem?id=1422
タイトル:
       都市には交点->交点(方向)で街(回路が存在しない)が表示されます.空襲の時、どのように最小の傘兵(交差点の交差点に置く)を下げる必要があるかを聞いて、傘兵が同じ交差点を繰り返さない条件の下で、すべての傘兵が完全な都市のすべての交差点を遍歴することができるようにします.
分析:
       実は傘兵一人一人が歩いているのは方向性のある簡単な道です.我々が要求するのは,このDAG図の最小数の単純な経路ですべてのノードをカバーすることができ,任意の2つの経路で重複しないノードである.これがDAGの最小パスオーバーライドの問題です.
       DAG最小パスオーバーライド問題の解=ノード数−二分図の最大マッチング.
       まず、DAGの各点を二分図の左右の点セットに1回保存し、DAGのエッジi->jについては、二分図にエッジ左i->右jを追加します.その後、この二分図の最大一致辺数を求めればよい.
ACコード:

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=120+5;

struct Max_Match
{
    int n;
    vector<int> g[maxn];
    bool vis[maxn];
    int left[maxn];

    void init(int n)
    {
        this->n=n;
        for(int i=1; i<=n; ++i) g[i].clear();
        memset(left,-1,sizeof(left));
    }

    bool match(int u)
    {
        for(int i=0;i<g[u].size();++i)
        {
            int v=g[u][i];
            if(!vis[v])
            {
                vis[v]=true;
                if(left[v]==-1 || match(left[v]))
                {
                    left[v]=u;
                    return true;
                }
            }
        }
        return false;
    }

    int solve()
    {
        int ans=0;
        for(int i=1; i<=n; ++i)
        {
            memset(vis,0,sizeof(vis));
            if(match(i)) ++ans;
        }
        return ans;
    }
}MM;

int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        MM.init(n);
        while(m--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            MM.g[u].push_back(v);
        }
        printf("%d
",n-MM.solve());
    }
    return 0;
}