【Acwing】最小生成树联络员

左手的ㄟ右手 2024-03-31 10:43 84阅读 0赞

[1143. 联络员 - AcWing题库][1143. _ - AcWing]

题意：

![fe41e24a599a40f7b7598a96b60fda66.png][]

思路：

把必选的都选上，然后其他的按最小生成树来做就好了

具体到代码上就是：按p从小到大排序，然后去做一遍最小生成树就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=2e3+10,mxe=1e4+10;
    struct ty{
        int p,u,v,w;
    }edge[mxe<<1];
    bool cmp(ty x,ty y){
        if(x.p==y.p) return x.w<y.w;
        return x.p<y.p;
    }
    int n,m,p,x,y,w;
    int f[mxn];
    int find(int x){
        return f[x]=(x==f[x])?x:find(f[x]);
    }
    void join(int u,int v){
        int f1=find(u),f2=find(v);
        if(f1!=f2) f[f1]=f2;
    }
    int kruskal(){
        int ans=0;
        sort(edge+1,edge+1+m,cmp);
        //for(int i=1;i<=m;i++) cout<<edge[i].p<<" "<<edge[i].u<<" "<<edge[i].v<<" "<<edge[i].w<<'\n';
        for(int i=1;i<=m;i++){
            if(find(edge[i].u)==find(edge[i].v)&&edge[i].p==2) continue;
            join(edge[i].u,edge[i].v);
            ans+=edge[i].w;
            //cout<<edge[i].w<<'\n';
        }
        return ans;
    }
    void init(){
        for(int i=1;i<=n;i++) f[i]=i;
    }
    int main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cin>>n>>m;
        init();
        for(int i=1;i<=m;i++){
            cin>>p>>x>>y>>w;
            edge[i]={p,x,y,w};
        }
        cout<<kruskal()<<'\n';
    }

[1143. _ - AcWing]: https://www.acwing.com/problem/content/description/1145/
[fe41e24a599a40f7b7598a96b60fda66.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/e5b95bfbcf12428ea038581688bb2a2f.png

发表评论取消回复

表情：

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

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

相关阅读

相关【Acwing】最小生成树新的开始

[1146. 新的开始 - AcWing题库][1146. _ - AcWing] 题意： ![3a1a7b00e901471683c719cc62a6c82e.png][

àì夳堔傛蜴生んèń/ 2024年03月31日 10:43/ 0 赞/ 63 阅读

相关【Acwing】最小生成树联络员

[1143. 联络员 - AcWing题库][1143. _ - AcWing] 题意： ![fe41e24a599a40f7b7598a96b60fda66.png][]

左手的ㄟ右手/ 2024年03月31日 10:43/ 0 赞/ 85 阅读

相关【Acwing】最小生成树繁忙的都市

[1142. 繁忙的都市 - AcWing题库][1142. _ - AcWing] 题意： ![6713fc4c4e764ab4a0cf4d5daabd9296.png]

冷不防/ 2024年03月31日 10:42/ 0 赞/ 82 阅读

相关 Kruskal AcWing 859. Kruskal算法求最小生成树

Kruskal AcWing 859. Kruskal算法求最小生成树原题链接 [AcWing 859. Kruskal算法求最小生成树][AcWing 859.

叁歲伎倆/ 2023年09月28日 12:49/ 0 赞/ 28 阅读

相关 Prim AcWing 858. Prim算法求最小生成树

Prim AcWing 858. Prim算法求最小生成树原题链接 [AcWing 858. Prim算法求最小生成树][AcWing 858. Prim]

逃离我推掉我的手/ 2023年09月28日 12:49/ 0 赞/ 170 阅读

相关生成树最小生成树_最小生成树

生成树最小生成树 Problem statement: 问题陈述： Given a weighted undirected graph. Find the sum of

我就是我/ 2023年03月05日 09:43/ 0 赞/ 27 阅读

相关生成树相关问题（最小生成树变形，次小生成树，最小度限度生成树，极差最小生成树）

生成树相关问题（最小生成树变形，次小生成树，最小度限度生成树，极差最小生成树）视频：[https://www.bilibili.com/video/BV1G64y187ke

Bertha 。/ 2022年09月12日 05:52/ 0 赞/ 235 阅读

相关 WUST 1947 联络员（最小生成树+部分连好的点）

1947: 联络员 Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld Submitted: 1

刺骨的言语ヽ痛彻心扉/ 2022年06月12日 04:55/ 0 赞/ 83 阅读

相关最小生成树

问题提出：要在n个城市间建立通信联络网。顶点：表示城市，权：城市间通信线路的花费代价。希望此通信网花费代价最小。问题分析：答案只能从生成树中找，因为要做到任何

雨点打透心脏的1/2处/ 2022年03月18日 12:28/ 0 赞/ 326 阅读

相关最小生成树

Jungle Roads [http://poj.org/problem?id=1251][http_poj.org_problem_id_1251] Descrip

逃离我推掉我的手/ 2021年11月29日 22:28/ 0 赞/ 473 阅读