为啥不开O2能AC,开了就MLE
  • 板块P1111 修复公路
  • 楼主makerY
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/7/28 11:35
  • 上次更新2023/11/3 07:15:45
查看原帖
为啥不开O2能AC,开了就MLE
642544
makerY楼主2023/7/28 11:35

rt

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2010,M=100010;
int f[N],n,m,x,y,t;
struct Edge
{int a,b,t;}e[M];
bool cmp(Edge x,Edge y)
{
	return x.t<y.t;
}
int find(int x)
{
	if(x!=f[x]) return f[x]=find(f[x]);
} 
int main()
{
	scanf("%d%d",&n,&m);
	int cnt=n;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].t);
		f[e[i].a]=e[i].a,f[e[i].b]=e[i].b;
	}
	sort(e+1,e+1+m,cmp);
	bool flag=0;
	for(int i=1;i<=m;i++)
	{
		int fx=find(e[i].a),fy=find(e[i].b);
		if(fx!=fy) f[fx]=fy,cnt--;
		if(!flag&&cnt==1) printf("%d",e[i].t),flag=1;
	}
	if(flag==0) printf("-1");
	return 0;
}

2023/7/28 11:35
加载中...