Luogu P1525 【关押罪犯】

电玩女神 2023-06-02 13:59 1阅读 0赞

跟P1892团伙的做法类似。

除了用数组保存敌人编号之外，还有另一种做法。

团伙：合并时，用i节点表示为友，i+n结点表示为敌。

本题：合并时，用i节点表示同一监狱，i+n结点表示不同监狱。

按边权从大到小枚举边，贪心地把边连接的两个结点设定为不同监狱（为敌）

遇到冲突后说明必须在同一个监狱，此时输出权值，即为冲突的最大值。

#include<cstdio>
    #include<algorithm>
    using namespace std;
    
    int n,m,cnt,fa[100005],ans;
    
    struct edge{
        int u,v,w;
    }e[100005];
    
    inline void add(int u,int v,int w){
        e[++cnt].u=u;
        e[cnt].v=v;
        e[cnt].w=w;
    }
    
    inline int cmp(edge x,edge y){
        return x.w>y.w;
    }
    
    inline int getfa(int v){
        if(fa[v]==v)return v;
        fa[v]=getfa(fa[v]);
        return fa[v];
    }
    
    inline void merge(int x,int y){
        x=getfa(x);y=getfa(y);
        fa[y]=x;
    }
    
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=2*n;i++)fa[i]=i;
        for(int i=1;i<=m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }
        sort(e+1,e+cnt+1,cmp);
        for(int i=1;i<=cnt;i++){
            int u=e[i].u,v=e[i].v;
            int fau=getfa(u),fav=getfa(v);
            if(fau!=fav){
                merge(u,v+n);
                merge(v,u+n);
            }
            else{
                printf("%d\n",e[i].w);
                return 0;
            }
        }
        printf("0\n");//洛谷第一个点卡0
    }

转载于:https://www.cnblogs.com/Y15BeTa/p/11427577.html

发表评论取消回复

表情：

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

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

相关阅读

相关 codevs1069 关押罪犯贪心+并查集

题目描述 Description S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随

不念不忘少年蓝@/ 2024年02月17日 19:48/ 0 赞/ 71 阅读

相关 Luogu P1525 【关押罪犯】

跟P1892团伙的做法类似。除了用数组保存敌人编号之外，还有另一种做法。团伙：合并时，用i节点表示为友，i+n结点表示为敌。本题：合并时，用i节点表示同一监狱，i+

电玩女神/ 2023年06月02日 13:59/ 0 赞/ 2 阅读

相关 LuoGu P1368 工艺

[LuoGu P1368 工艺][LuoGu P1368] 最小表示法的板子题.这个题可以用\\(n\\:log\_2\\:n\\)的\\(SA\\)求最小表示法也可以用更

雨点打透心脏的1/2处/ 2023年06月02日 11:59/ 0 赞/ 34 阅读

相关 P1525 关押罪犯

[P1525 关押罪犯][P1525] 提供一种做法：并查集。考虑a和b之间有仇恨关系，存入结构体中。因为有对应关系，且结构体带有权值，答案求最值，考虑排序。如

我会带着你远行/ 2023年06月01日 08:45/ 0 赞/ 18 阅读

相关 Luogu P3254 圆桌问题

[题目链接 \\(Click\\) \\(Here\\)][_Click_ _Here] 水题。记得记一下边的流量有没有跑完。 include <bits/st

傷城~/ 2022年01月09日 10:49/ 0 赞/ 184 阅读

相关 CH4901/洛谷1525 关押罪犯（贪心+并查集or二分+二分图染色）

题意：有n个罪犯，其中有m对憎恨关系，表示a和b的怨气值为c。把这n个罪犯放到两个监狱中，使每个监狱里中最大的两罪犯的怒气值最小。输出这个最大的怒气值。分析：挺简单的

我就是我/ 2021年11月13日 23:18/ 0 赞/ 236 阅读

相关 P1046【NOIP2010-3】关押罪犯

<table> <tbody> <tr> <td> <table> <tbody> <tr> <td><s

心已赠人/ 2021年11月01日 14:38/ 0 赞/ 231 阅读

相关 luogu P3146 （区间dp）

[传送门][Link 1] 题意：有一行格子，每个格子都有一个数值，如果相邻两个格子相同的话，可以合并成一个新的格子，新的格子的值为原来的值+1。现在问你通过不断的合

叁歲伎倆/ 2021年11月01日 09:10/ 0 赞/ 535 阅读

相关 [Luogu P1542] 包裹快递

[原题链接qwq][qwq] \\(Structure\\) 本题要求我们求出 `车的最大速度最小值` 。像求 `最大值最小`、`最小值最大` 这种类型的题目，我们

刺骨的言语ヽ痛彻心扉/ 2021年10月25日 11:57/ 0 赞/ 329 阅读

相关 LuoGu P1006 传纸条

[题目传送门][Link 1] 这题嘛...方格取数和这题一样一样的只不过这题是从左上到右下再回去罢了（来回一趟和来两趟有区别么？没有，那么这题和上题用一样的转移和状态就

你的名字/ 2021年10月01日 03:50/ 0 赞/ 276 阅读