游戏 | 二分图匹配、并查集

[SCOI2010]游戏

https://ac.nowcoder.com/acm/problem/20566

题目大意:
每个装备给出两个属性值,每次只能选择一个

从1的属性值开始选,每个装备只能选择一次,并且只能选择一个属性,问最多选择几个?

题目思路:
一个经典的套路

因为路径已经确定,所以也就硬性要求了这一步该选什么

1 2

3 1

这个样例来说,假设第一件装备选择了1,那么第二件装备就没法选择,但是你会发现可以选择两个。

此时有没有一种方法可以使得1选2,2去选1呢

模拟这个过程,其实就是匈牙利匹配的过程

所以搞一个匈牙利匹配即可

Code:

/*** keep hungry and calm CoolGuang!***/
ll n,m,p;
vector<int>v[maxn];
int vis[maxn],match[maxn];
int dfs(int u){
    for(int e:v[u]){
        if(!vis[e]){
            vis[e] = 1;
            if(!match[e]||dfs(match[e])){
                match[e] = u;
                return 1;
            }
        }
    }return 0;
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++){
        int x,y;scanf("%d%d",&x,&y);
        v[x].push_back(i);
        v[y].push_back(i);
    }
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(!dfs(i)){
            printf("%d\n",i-1);
            return 0;
        }
    }
    printf("%d\n",n);
    return 0;
}
/**
6 8
1 2 1
1 3 1
3 4 1
2 5 1
4 6 1
5 6 1
2 4 1
***/

Extend:
考虑这种问题有一种并查集的普遍解法?

问题形如2020牛客多校某场的一个题

这个题顺序维护就好了

Code:

/*** keep hungry and calm CoolGuang!***/
ll n,m,p;
int pre[maxn],sz[maxn],edg[maxn],rt[maxn],res[maxn];
int Find(int x){
    return pre[x] == x?x:pre[x] = Find(pre[x]);
}
int main()
{
    read(n);
    for(int i=1;i<=10001;i++){
        pre[i] = i;
        sz[i] = 1;
        edg[i] = 0;
    }
    for(int i=1;i<=n;i++){
        int x,y;scanf("%d%d",&x,&y);
        int dx = Find(x),dy = Find(y);
        if(dx != dy){
            pre[dy] = dx;
            sz[dx] += sz[dy];
            edg[dx] += edg[dy]+1;
        }else if(dx == dy) edg[dx]++;
    }
    for(int i=1;i<=10001;i++) rt[i] = Find(i);
    for(int i=1;i<=10001;i++){
        int k = i;
        while(k<=10001&&rt[k] == rt[i]) k++;
        k--;
        if(edg[rt[k]]<sz[rt[k]]){
            if(res[rt[k]]+k-i+1<=sz[rt[k]]-1) res[rt[k]] += k-i+1;
            else{
                int diff = sz[rt[k]]-1-res[rt[k]];
                printf("%d\n",i+diff-1);
                return 0;
            }
        }
        i = k;
    }
    return 0;
}
/**
3
1 2
3 1
3 3
***/
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利&nbsp;有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的&nbsp;真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
点赞 评论 收藏
分享
07-04 09:21
已编辑
Java
推拿大师:这是hr发的钓鱼贴吗
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务