50分注意
  • 板块P1396 营救
  • 楼主m_m_m
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/12/4 19:40
  • 上次更新2023/12/4 21:57:48
查看原帖
50分注意
481729
m_m_m楼主2023/12/4 19:40
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
int fa[20010];
int find(int x)
{
	if(fa[x]!=x)fa[x]=find(fa[x]);
	return fa[x];
}
struct dog{
	int u,v,w;
}a[20001];
bool cmp(dog q,dog e)
{
	return q.w <e.w ;
}
int main()
{
	cin>>n>>m>>s>>t;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].u >>a[i].v>>a[i].w; 
	}
	sort(1+a,1+a+m,cmp);
	for(int i=1;i<=m;i++)
	{
		int xx=find(a[i].u);
		int yy=find(a[i].v);
		if(xx!=yy)fa[xx]=yy;
		if(find(s)==find(t))//此处不能写成fa[s]==fa[t]{
			cout<<a[i].w ;
			return 0;
		}	
	}
	return 0;
	
}

2023/12/4 19:40
加载中...