HDU 1150(最小点覆盖)

迷南。 2022-09-20 11:21 152阅读 0赞

题意：经典的机器调度问题。

在二分图G=（X,Y;E）中求取最少的顶点集v\*（在｛X,Y｝中找），使得边ei （属于E）都和至少一个顶点vi（属于v\*）相关联。这就是二分图模型中的最小顶点覆盖问题。

最小点覆盖==二分图最大匹配。

#include <iostream>
    using namespace std;
    const int maxn=110;
    int map[maxn][maxn];
    int vis[maxn];
    int n,m,k,x,y,link[maxn];
    int path(int u)
    {
        for(int v=1;v<m;v++)
        {
            if(map[u][v]&&!vis[v])
            {
                vis[v]=1;
                if(link[v]==-1||path(link[v]))
                {
                    link[v]=u;
                    return 1;
                }
            }
        }
        return 0;
    }
    int MaxMatch()
    {
        int res=0;
        memset(link,-1,sizeof(link));
        for(int i=1;i<n;i++)
        {
            memset(vis,0,sizeof(vis));
            if(path(i))
                res++;
        }
        return res;
    }
    int main()
    {
        int j;
        while(cin>>n&&n)
        {
            memset(map,0,sizeof(map));
            cin>>m>>k;  
            while(k--)
            {
                cin>>j>>x>>y;
                if(x!=0&&y!=0)// 看题目这一句At the beginning they are both work at mode_0.
                    map[x][y]=1;
            }
            cout<<MaxMatch()<<endl;
        } 
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu 题目1150 Machine Schedule（最小点覆盖）

[http://acm.hdu.edu.cn/showproblem.php?pid=1150 ][http_acm.hdu.edu.cn_showproblem.php_

冷不防/ 2022年12月22日 08:40/ 0 赞/ 183 阅读

相关 HDU 1150(最小点覆盖)

题意：经典的机器调度问题。在二分图G=（X,Y;E）中求取最少的顶点集v\（在｛X,Y｝中找），使得边ei （属于E）都和至少一个顶点vi（属于v\）相关联。这就是二分图模

迷南。/ 2022年09月20日 11:21/ 0 赞/ 153 阅读

相关 hdu 1151 最小路径覆盖

最小路径覆盖是选一个边的集合，使得这些边能够覆盖所有的顶点，并且这些边的数目是最小的。最小路径覆盖=顶点数-最大匹配数 Air Raid Time Limit:

太过爱你忘了你带给我的痛/ 2022年08月02日 12:46/ 0 赞/ 152 阅读

相关最小路径覆盖，最小点覆盖，最大独立点集

node 1：最小路径覆盖在一个ＰＸＰ的有向图中，路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路

青旅半醒/ 2022年08月02日 06:06/ 0 赞/ 182 阅读

相关 HDU3360-二分图最小点覆盖

National Treasures Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/3276

偏执的太偏执、/ 2022年07月12日 07:25/ 0 赞/ 172 阅读

相关 HDU3360-二分图最小点覆盖

National Treasures Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/3276

ゝ一世哀愁。/ 2022年07月12日 07:25/ 0 赞/ 160 阅读

相关 HDU1528-二分图最小点覆盖

Card Game Cheater Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768

我不是女神ヾ/ 2022年07月12日 07:20/ 0 赞/ 158 阅读

相关 HDU1528-二分图最小点覆盖

Card Game Cheater Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768

Love The Way You Lie/ 2022年07月12日 07:20/ 0 赞/ 162 阅读

相关 HDU1151- 最小路径覆盖

Air Raid Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/

墨蓝/ 2022年07月12日 05:03/ 0 赞/ 174 阅读

相关 HDU1150最小点覆盖

Machine Schedule Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768

我会带着你远行/ 2022年07月12日 05:02/ 0 赞/ 182 阅读