繁忙的都市

川长思鸟来 2021-11-13 15:10 236阅读 0赞

[题面][Link 1]

主要思路就是将所有的边储存起来，然后进行贪心地选择，期间需要判断两个端点是否有关联，这一过程通过并查集实现。

1 #include <iostream> 
     2 #include <cstdio>
     3 #include <algorithm>
     4 #include <cmath>
     5 using namespace std;
     6 
     7 const int maxn = 500;
     8 
     9 int n, m;
    10 int x[maxn], y[maxn], f[maxn];
    11 int ans = 0;
    12 
    13 struct node {
    14     int x, y;
    15     int val;
    16 }dis[50100];
    17 
    18 bool cmp(node a, node b) {
    19     return a.val < b.val;
    20 }
    21 
    22 int find(int x) {
    23     int r = x;
    24     while(r != f[r]) r = f[r];
    25     int i = x, j;
    26     while(f[i] != r) {  
    27         j = f[i];  
    28         f[i] = r;  
    29         i = j;  
    30     }
    31     return r;  
    32 }
    33 
    34 void merge(int x, int y) {
    35     x = find(x);
    36     y = find(y);
    37     if(x != y) f[y] = x;
    38 }
    39 
    40 int main() {
    41     cin >> n >> m;
    42     for(int i = 1; i <= m; i++) {
    43         cin >> dis[i].x >> dis[i].y >> dis[i].val;
    44     }
    45     for(int i = 1; i <= n; i++) f[i] = i;
    46 
    47     sort(dis + 1, dis + m + 1, cmp);
    48     int tmp = 0, maxn = 0;
    49     for(int i = 1; i <= m; i++) {
    50         if(find(dis[i].x) != find(dis[i].y)) {
    51             merge(dis[i].x, dis[i].y);
    52             tmp++;
    53             maxn = max(maxn, dis[i].val);
    54         }
    55         if(tmp == n - 1) break;
    56     }
    57 
    58     cout << tmp << ' ' << maxn;
    59 }

转载于:https://www.cnblogs.com/ainiyuling/p/11149938.html

[Link 1]: https://www.luogu.org/problemnew/show/P2330

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 P2330 [SCOI2005]繁忙的都市

题目描述城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相

╰半夏微凉°/ 2023年07月12日 01:29/ 0 赞/ 27 阅读

相关 P2330-[SCOI2005]繁忙的都市

1 include <bits/stdc++.h> 2 using namespace std; 3 define pb push_back

墨蓝/ 2023年06月01日 08:55/ 0 赞/ 21 阅读

相关极の都市---贪心算法

目录一：逃脱游戏：二：找硬币问题：三：活动问题：四：最小数字问题：五：两个数字的最小和:

秒速五厘米/ 2022年12月21日 03:28/ 0 赞/ 129 阅读

相关修改密码服务器繁忙,找回密码服务器繁忙

找回密码服务器繁忙内容精选换一换 ![c8a5a5028d2cabfeeee0907ef5119e7e.png][] 如果Linux操作系统弹性云服务器未安装密码重置

爱被打了一巴掌/ 2022年09月03日 11:19/ 0 赞/ 19 阅读

相关 WUST 1946 繁忙的都市（最小生成树+克鲁斯卡尔算法）

1946: 繁忙的都市 Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld Submitted:

女爷i/ 2022年06月12日 04:45/ 0 赞/ 128 阅读

相关繁忙的都市

[题面][Link 1] 主要思路就是将所有的边储存起来，然后进行贪心地选择，期间需要判断两个端点是否有关联，这一过程通过并查集实现。 1 include <ios

川长思鸟来/ 2021年11月13日 15:10/ 0 赞/ 237 阅读

相关解决oracle数据库资源繁忙

![在这里插入图片描述][2019080715425140.png] 删除这个操作对应的会话。如下：输入： SELECT sid, serial\, usern

分手后的思念是犯贱/ 2021年11月04日 16:16/ 0 赞/ 370 阅读

相关 VMware无法关机虚拟机繁忙

在使用VM ware过程中，我们经常会遇到这种情况：虚拟机无法关闭，并且VMware进程无法关闭，需要重启计算机删除安装包里面的锁定文件 .lck .vmem 后缀的文件,这个

爱被打了一巴掌/ 2021年07月26日 23:53/ 0 赞/ 837 阅读