美文网首页GraphTheory
POJ-1422-Air Raid(二分图-最小不相交路径覆盖)

POJ-1422-Air Raid(二分图-最小不相交路径覆盖)

作者: 雨落八千里 | 来源:发表于2019-08-21 21:32 被阅读0次

    Air Raid

    题意:

    • 在有向无环图中,每个伞兵可以沿着街道参观其他十字路口,输出尽可能少的伞兵数量可以访问所有的十字路口(一个路口只能被一个士兵参观)

    思路:

    • 最小不相交路径覆盖(就是以最少的路径覆盖所有的点),将士兵的路程看作一条路径

    最小不相交路径覆盖==原图总点数-对应二分图的最大边匹配

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    #include<vector>
    using namespace std;
    vector<int>vep[130];
    int match[130];
    int vis[130];
    int Hungarian(int x)
    {
        for(int i=0;i<vep[x].size( );i++)
        {
            int v=vep[x][i];
            if(!vis[v])
            {
                vis[v]=1;
                if(match[v]==-1||Hungarian(match[v]))
                {
                    match[v]=x;
                    return 1;
                }
            }
        }
        return 0;
    }
    int main( )
    {
        int n,m,x,y;
        int t;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++)
            {
                vep[i].clear( );
            }
            for(int i=1;i<=m;i++)
            {
                scanf("%d%d",&x,&y);
                vep[x].push_back(y);
            }
            memset(match,-1,sizeof(match));
            int ans=0;
            for(int i=1;i<=n;i++)
            {
                memset(vis,0,sizeof(vis));
                if(Hungarian(i))
                {
                    ans++;
                }
            }
            printf("%d\n",n-ans);
        }
        return 0;
    }
    

    相关文章

      网友评论

        本文标题:POJ-1422-Air Raid(二分图-最小不相交路径覆盖)

        本文链接:https://www.haomeiwen.com/subject/mphwsctx.html