2 条题解

  • 0
    @ 2025-2-21 18:10:53
    #include <bits/stdc++.h>
    using namespace std;
    struct Node
    {
    	int x,y,t;
    } a[10010];
    int f[510];
    int find(int x)
    {
    	if (f[x]!=x) f[x]=find(f[x]);
    	return f[x];
    }
    bool cmp(Node a,Node b)
    {
    	return a.t<b.t;
    }
    int main()
    {
    	int n,m;
    	//freopen("city.in","r",stdin);
    	//freopen("city.out","w",stdout);
    	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,cmp);
    	int cnt=n-1,ans=0;
    	for(int i=1;i<=m;i++)
    	{
    		int px=find(a[i].x);
    		int py=find(a[i].y);
    		if(px==py)continue;
    		cnt--;
    		ans++;
    		f[py]=px;
    		if (cnt==0)
    		{
    			cout<<ans<<" "<<a[i].t<<endl;
    			return 0;
    		}
    	}
    	return 0;
    }
    

    信息

    ID
    6371
    时间
    1000ms
    内存
    125MiB
    难度
    3
    标签
    递交数
    2
    已通过
    2
    上传者