5 条题解

  • -6
    @ 2023-7-17 16:08:56

    AC

    #include <bits/stdc++.h>
    #define IOS ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    #define re register
    #define int long long
    using namespace std;
    typedef long long ll;
    struct node
    {
    	int strt;
    	int to;
    	int len;
    };
    bool cmp(node x, node y)
    {
    	return x.len<y.len;
    }
    int n, m, x, y, z, ans;
    vector<node> edges;
    int parent[500010];
    int fnd(int t)
    {
    	return (parent[t]==t?t:parent[t]=fnd(parent[t]));
    }
    signed main()
    {
    	IOS;
    	cin>>n>>m;
    	for(int i=1; i<=n; i++) parent[i]=i;
    	for(int i=0; i<m; i++) cin>>x>>y>>z, edges.push_back({x, y, z});
    	sort(edges.begin(), edges.end(), cmp);
    	for(int i=0; i<m; i++)
    	{
    		if(fnd(edges[i].strt)!=fnd(edges[i].to))
    		{
    			parent[fnd(edges[i].strt)]=fnd(edges[i].to);
    			ans=max(ans, edges[i].len);
    		}
    	}
    	cout<<ans;
    	return 0;
    }
    
    

    信息

    ID
    474
    时间
    1000ms
    内存
    128MiB
    难度
    3
    标签
    递交数
    148
    已通过
    75
    上传者