最小生成树10pts求救
  • 板块P1396 营救
  • 楼主dist_22r
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/3/21 12:55
  • 上次更新2023/10/23 20:57:37
查看原帖
最小生成树10pts求救
593255
dist_22r楼主2023/3/21 12:55
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,m,maxn,a,b,f[N];
struct e{
	int u,v,w;
}ed[N];
bool cmp(e x,e y)
{
	return x.w<y.w;
}
int find(int x)
{
	if(f[x]==x)
		return x;
	else
		return f[x]=find(f[x]);
}
void kruskal()
{
	int s=0,cnt=0;
	sort(ed+a,ed+b+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int u=find(ed[i].u),v=find(ed[i].v),w=ed[i].w;
		if(u!=v)
		{
			f[u]=v;
			if(w>=maxn)
				maxn=w;
			cnt++; 
		}
	}
	cout<<maxn<<endl;
}
int main()
{
	cin>>n>>m;
	cin>>a>>b;
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		ed[i]={x,y,w};
	}
	kruskal();
	return 0;
}

https://www.luogu.com.cn/record/105384742 五颜六色测试点

2023/3/21 12:55
加载中...