CF F. Royal Questions kruskal

快来打我* 2021-11-17 16:20 249阅读 0赞

Code:

#include<bits/stdc++.h> 
    #define ll long long  
    #define maxn 200004 
    using namespace std;  
    void setIO(string s) {
        string in=s+".in"; 
        freopen(in.c_str(),"r",stdin); 
    }
    int n,m;   
    int p[maxn],tag[maxn]; 
    void init() {
        for(int i=0;i<maxn;++i) p[i]=i;  
    } 
    int find(int x) {
        return p[x]==x?x:p[x]=find(p[x]);  
    }
    struct Edge { 
        int u,v,c; 
    }ed[maxn];         
    bool cmp(Edge a,Edge b) {
        return a.c>b.c; 
    }
    int main() {
        // setIO("input");  
        init(); 
        scanf("%d%d",&n,&m);   
        for(int i=1;i<=m;++i) scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].c);   
        sort(ed+1,ed+1+m,cmp);  
        ll ans=0; 
        for(int i=1;i<=m;++i) {
            int a=find(ed[i].u), b=find(ed[i].v);       
            if(a!=b&&(!tag[a]||!tag[b])) ans+=1ll*ed[i].c, tag[a]|=tag[b], p[b]=a; 
            else if(a==b && !tag[a]) ans+=1ll*ed[i].c, tag[a]=1;         
        }   
        printf("%I64d\n",ans); 
        return 0; 
    }

转载于:https://www.cnblogs.com/guangheli/p/11263392.html

发表评论取消回复

表情：

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

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

相关阅读

相关 CF713div3 F

[Problem - F - Codeforces][] 题意：小明想买一个价值为c的东西，他开始打工，他一开始在第i个职务，每天可以挣a\[i\]，他也可以用一天的时间

你的名字/ 2024年03月27日 16:20/ 0 赞/ 121 阅读

相关【01trie】CF1851F

[Problem - F - Codeforces][] 题意： ![cc8869e75b7b4f14ad11f61c54146dfb.png][] ![821c4d9f

清疚/ 2024年03月22日 21:07/ 0 赞/ 112 阅读

相关【暴力DP】CF1409 F

[Problem - F - Codeforces][] 题意： ![0b383875a1444f75b1163b33ac695a0b.png][] ![e01ceb20

骑猪看日落/ 2024年03月01日 07:49/ 0 赞/ 73 阅读

相关【MST】 CF1108 F

[Problem - 1108F - Codeforces][] 题意 ![07383efd93574c469ced2ac218c96344.png][] ![89bbb

阳光穿透心脏的1/2处/ 2024年02月22日 04:15/ 0 赞/ 85 阅读

相关【CF765F】Souvenirs

[题目][Link 1] 仔细思考发现我会\\(O((n+m)\\sqrt\{n\}\\log n)\\)，不难发现这显然过不了考虑一下这道题的答案是某一个点对产生的贡献

向右看齐/ 2023年10月11日 11:20/ 0 赞/ 77 阅读

相关分块——cf1207F

这么傻逼的题当时想了那么久用a数组维护原序列，b\[i\]\[j\]表示 pos%i=j 的 a\[pos\]之和对于每个修改1 x y，先直接修改a\[x\]，然后枚

桃扇骨/ 2023年10月11日 09:09/ 0 赞/ 47 阅读

相关【CF1215F】 Radio Stations

[题目][Link 1] 比较精妙的\\(\\text\{2-sat\}\\)建图了还是按照套路把每个电台拆成\\((0/1,i)\\)表示不选/选前两种连边是板子就

朱雀/ 2023年10月11日 05:27/ 0 赞/ 24 阅读

相关 CF F. Royal Questions kruskal

Code: include<bits/stdc++.h> define ll long long define maxn 200004

快来打我*/ 2021年11月17日 16:20/ 0 赞/ 250 阅读

相关 CF1063F String Journey

[CF1063F String Journey][] 法一： [题解][Link 1] 首先发现，答案一定可以是长度为k,k-1,....1的串而且后一个是前一个

蔚落/ 2021年11月13日 15:36/ 0 赞/ 251 阅读

相关 CF572_Div2_F

题意 [http://codeforces.com/contest/1189/problem/F][http_codeforces.com_contest_1189_pr

╰半夏微凉°/ 2021年10月29日 13:32/ 0 赞/ 337 阅读