bzoj1083 [SCOI2005]繁忙的都市 洛谷2330

题目描述
城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市C的道路是这样分布的:城市中有n个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连接。这些道路是双向的,且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值,分值越小表示这个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的要求:

1.改造的那些道路能够把所有的交叉路口直接或间接的连通起来。 2.在满足要求1的情况下,改造的道路尽量少。 3.在满足要求1、2的情况下,改造的那些道路中分值最大的道路分值尽量小。

任务:作为市规划局的你,应当作出最佳的决策,选择那些道路应当被修建。

输入输出格式
输入格式:
第一行有两个整数n,m表示城市有n个交叉路口,m条道路。

接下来m行是对每条道路的描述,u, v, c表示交叉路口u和v之间有道路相连,分值为c。(1≤n≤300,1≤c≤10000,1≤m≤50000)

输出格式:
两个整数s, max,表示你选出了几条道路,分值最大的那条道路的分值是多少。

输入输出样例
输入样例#1:
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8
输出样例#1:
3 6
sb 最小生成树

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <cstdio>
#include <queue>
#include <cmath>
#define inf 100000000
using namespace std;
int n,m;
struct dmf{
    int x,y,z;
}duan2[10005];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
  if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline bool cmp(dmf a,dmf b){
    return a.z<b.z;
}
int fa[100005];
int findfa(int x){
    if(fa[x]!=x) fa[x]=findfa(fa[x]);
    return fa[x];
}
void build_tree(){
    int k=0;
    int ans=0;
    for(int i=1;i<=m;i++){
        int xx=duan2[i].x;
        int yy=duan2[i].y;
        int xxx=findfa(xx);
        int yyy=findfa(yy);
        if(xxx!=yyy){
            fa[xxx]=yyy;
            ans=max(ans,duan2[i].z);
            k++;
        }
        if(k==n-1) break;
    }
    printf("%d",ans);
}
int main(){
    n=read();
    m=read();
    for(int i=1;i<=m;i++){
        duan2[i].x=read();
        duan2[i].y=read();
        duan2[i].z=read();
    }
    sort(duan2+1,duan2+1+m,cmp);
    for(int i=1;i<=n;i++) fa[i]=i;
    printf("%d ",n-1);
    build_tree();
    return 0;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-20 07:39
门头沟学院_2023
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
投票
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-16 02:48
门头沟学院_2022
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议