CSUST选拔赛题解之-Problem A: 灾区重建

时间:2022-12-20 23:12:43

Problem A: 灾区重建

Time Limit: 3 Sec   Memory Limit: 128 MB
Submit: 114   Solved: 31
[ Submit][ Status][ Web Board]

Description

    在一场地震之后,原本美丽的C国变成了一片废墟,但是这并没有击垮人们的意志,在各方的支持下救援队马上开始了灾区重建。已知C国一共由N个城市(编号从1~N)组成,在这N个城市之间有M条道路连通着各个城市,现在要将物资运往各个城市,但是每条道路都有其最大承重量W,也就是说如果一辆车所运载的货物重量大于W的话是无法通过这条路的。为了防止道路崩塌同时提高效率,我们都会去走承重量尽可能大的道路,现在救援队的队长想知道如果要将货物从任意一个城市运往其他N-1个城市,一次所能运输的最大重量是多少,你能告诉他吗?

Input

输入第一行为一个整数T(T<=10),表示有T组样例;

第二行为两个整数N(N<=10^5)和M(M<=10^6),分别表示城市的数量和道路的数量;

接下来M行每行有三个整数,u,v,w,(u,v<=N,w<=10^9)

表示u和v之间有一条承重量为w的道路(道路是双向的,即可以从u走到v,也可以从v走到u,同时数据保证任意两个城市之间至多只会有一条道路)。


Output

每组样例输出一行

Case #X: Y,X表示第几组样例,Y便是所要求的答案。

Sample Input

1
4 6
1 2 2
1 3 1
1 4 9
2 4 8
2 3 10
3 4 4

Sample Output

Case #1: 8

HINT


样例解释:



如果要将物资从1运输到2,那么走1-4-2这条路径所即能运输的最大重量为8;



如果要将物资从1运输到3,那么走1-4-2-3这条路径即所能运输的最大重量为8;



如果要将物资从1运输到4,那么走1-4这条路径即所能运输的最大重量为9;



如果要将物资从2运输到3,那么走2-3这条路径即所能运输的最大重量为10;



如果要将物资从2运输到4,那么走2-4这条路径即所能运输的最大重量为8;



如果要将物资从3运输到4,那么走3-2-4这条路径即所能运输的最大重量为8;



故答案为8。

解题思路:读题后发现这道题是一个最大生成树,只要你做过 寒训的最小生成树,那么这道题你一定会做,我们先按照每条路的承重量从大到小排个序,然后开始建路(并查集),输出所有城市达到连通时所建的最后那条路即可!唉。。。比赛时太紧张把路的数组开成了1e5,结果一直RE,到最后还是没发现,直到补题的时候才发现。。。简直气死我了。。。都怪自己太菜了 ╯︿╰。。。

AC代码:
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<time.h>
#include<map>
#include<string>
#include<algorithm>
#include<set>
#define N 100010
 
using namespace std;
 
int root[N], sum, maxd;
 
struct node
{
    int x;
    int y;
    int num;
}road[1000010];
 
bool cmp(node a, node b)
{
    return a.num > b.num;
}
 
int formalset(int n)
{
    for(int i = 1; i <= n ;i ++)
    {
        root[i] = i;
    }
}
 
int find_root(int k)
{
    if(root[k] != k)
        root[k] = find_root(root[k]);
    return root[k];
}
 
void merge_root(int a, int b, int c)
{
    if(find_root(a) == find_root(b))
        return;
    sum --;
    maxd = c;
    root[find_root(b)] = find_root(a);
}
 
int main()
{
    int T, n, m, k = 1;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        formalset(n);
        sum = n - 1;
        for(int i = 0; i < m; i ++)
        {
            scanf("%d%d%d", &road[i].x, &road[i].y, &road[i].num);
        }
        sort(road, road + m, cmp);
        for(int i = 0; i < m ; i++)
        {
            if(sum == 0) break; //所有城市连通
            merge_root(road[i].x, road[i].y, road[i].num);
        }
        printf("Case #%d: %d\n", k++, maxd);
    }
    return 0;
}