POJ 1422【最小路覆盖数】

题意：

背景：

小镇有n个路口，空降兵可以在任意路口降落。有m条通往别的路口的单向边，但是不会出现循环。

问最少空降多少个士兵可以走完所有路口。

数据输入：

测试组数 t

每组有：

路口数 n

边数 m

接下来m组，每组a b代表a到b的单向边。

思路：

这是一个朴素的最小路覆盖数问题。

定理：最小路覆盖数=节点数-最大匹配数。

二分匹配的匈牙利算法不重复。

【菜鸟第一次写最大匹配，代码的错误在于当找到来源是本身的时候继续递归了】

/*************************************************************************

       > File Name: F.cpp

       > Author: ttpond

       > Created Time: 2015-8-17 9:55:53

************************************************************************/

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<iostream>

#include<math.h>

#include<vector>

#include<map>

#include<queue>

#include<stack>

using namespace std;

vector<int>tmp[];

bool vis[];

int from[];

int ans=;

void dfs(int n)

{

    vector<int>::iterator it;

    for(it=tmp[n].begin();it!=tmp[n].end();it++)

    {

        if(!vis[*it])

        {

            from[*it]=n;

            vis[*it]=;

            ans++;

            break;

        }

        else

        {

            if(from[*it]!=n)

                dfs(from[*it]);

        }

    }

}

int main()

{

    int t,tt,v,e;

    scanf("%d",&t);

    for(tt=;tt<t;tt++)

    {

        ans=;

        memset(vis,,sizeof(vis));

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

        for(int i=;i<=v;i++)

            tmp[i].clear();

        for(int i=;i<e;i++)

        {

            int a,b;

            scanf("%d%d",&a,&b);

            tmp[a].push_back(b);

        }

        for(int i=;i<=v;i++)

            dfs(i);

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

    }

    return ;

}

巴特西

POJ 1422【最小路覆盖数】

最新文章

热门文章