洛谷P1111 修复公路

基本思路

一个结构体存储操作，另外一个存储节点，操作按时间排序并遍历即可。

#include<bits/stdc++.h>
using namespace std;
typedef struct
{
    int vertex,next,time;
}OP;OP op[100010];
typedef struct{
    int parent;
    int child;
}NODE; NODE nodes[5000];
int n,m;
bool cmp(OP n1,OP n2)
{
    return n1.time<n2.time;
}
int find(int key)
{
    if(nodes[key].parent!=key)
        return nodes[key].parent=find(nodes[key].parent);
    return nodes[key].parent;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        nodes[i].child=1;
        nodes[i].parent=i;
    }
    int cnt=0;
    while(m--)
    {
        cin>>op[cnt].vertex>>op[cnt].next>>op[cnt].time;
        cnt++;
    }
    sort(op,op+cnt,cmp);
//  for(int i=0;i<cnt;i++)
//  {
//      cout<<op[i].time<<" ";
//  }
//  cout<<endl;
    for(int i=0;i<=cnt;i++)
    {
        if(i==cnt)
        {
            cout<<-1<<endl;
            break;
        }
        int fa=find(op[i].vertex);
        int fb=find(op[i].next);
        if(fa!=fb)
        {
            nodes[fb].parent=fa;
            nodes[fa].child+=nodes[fb].child;
            nodes[fb].child=1;
        }
        if(nodes[fa].child==n)
        {
            cout<<op[i].time<<endl;
            break;
        }
    }
    return 0;
}

洛谷P1111 修复公路

原文：https://www.cnblogs.com/tldr/p/11144802.html