2 条题解

  • 1
    @ 2025-10-6 15:07:19
    #include<bits/stdc++.h>
    using namespace std;
    void read(int &h){
        char o;
        int x=0,y=1;
        o=getchar_unlocked();
        while(!(o<='9'&&o>='0')){
            if(o=='-'){
                y=-1;
            }
            o=getchar_unlocked();
        }
        while(o<='9'&&o>='0'){
            x*=10;
            x+=o-'0';
            o=getchar_unlocked();
        }
        h=x*y;
        return ;
    }
    const int N=1e5+10;
    struct road{
        int x,y,t;
    }a[N];
    int n,m,tree[N],u,v,o;
    bool cmd(road a,road b){
        return a.t<b.t;
    }
    int find_root(int x){
        if(tree[x]==x){
            return x;
        }
        return tree[x]=find_root(tree[x]);
    }
    void start(){
        o=n;
        for(int i=1;i<=n;i++){
            tree[i]=i;
        }
        return ;
    }
    int main(){
        ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
        read(n);read(m);
        start();
        for(int i=1;i<=m;i++){
            read(a[i].x);read(a[i].y);read(a[i].t);
        }
        sort(a+1,a+m+1,cmd);
        for(int i=1;i<=m;i++){
            u=find_root(a[i].x);
            v=find_root(a[i].y);
            if(u!=v){
                tree[u]=v;
                o--;
            }
            if(o==1){
                cout<<a[i].t<<" ";
                return 0;
            }
        }
        cout<<-1;
        return 0;
    }
    
    
    • -1
      @ 2024-12-27 19:57:40
      #include<bits/stdc++.h>//2
      using namespace std;
      const int N=100010;
      int f[N];
      struct Node{
          int x,y,t;
      }a[N];
       
      bool cmd(Node a,Node b)
      {
          return a.t<b.t;
      }
       
      int find(int x)
      {
          if(f[x]!=x) f[x]=find(f[x]);
          return f[x];
      }
       
      int main()
      {
          int n,m;
          scanf("%d%d",&n,&m);
          for(int i=1;i<=n;i++) f[i]=i;
          for(int i=1;i<=m;i++)
              scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);
          sort(a+1,a+m+1,cmd);
          int cnt=n-1;
          for(int i=1;i<=m;i++)
          {
              int fa=find(a[i].x);
              int fb=find(a[i].y);
              if(fa==fb) continue;
              f[fa]=fb;
              cnt--;
              if(cnt==0)
              {
                  printf("%d",a[i].t);
                  return 0;
              }
          }
          printf("-1");
          return 0;
      }
      
      • 1

      信息

      ID
      5169
      时间
      1000ms
      内存
      125MiB
      难度
      5
      标签
      递交数
      43
      已通过
      17
      上传者