板子为什么只拿10分。。。求助dalao
查看原帖
板子为什么只拿10分。。。求助dalao
284715
遮云壑楼主2021/6/18 07:06
#include<bits/stdc++.h>
#define maxn 100010
#define maxm 310
using namespace std;

inline void read(int& x)
{
	x=0;
	int y=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')y=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x=x*y;
}

struct edge{
	int u,v,w;
}e[maxn];
int cnt=0;
inline void add(int u,int v,int w)
{
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].u=u;
}

int n,m;

int fa[maxn];
bool cmp(edge a,edge b)
{
	return a.w<b.w;
}

int find(int x)
{
	if(x!=fa[x])fa[x]=find(fa[x]);
	return fa[x];
}

int ans=0;
inline void kruskal()
{
	int num=0;
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		int uu=e[i].u,vv=e[i].v,ww=e[i].w;
		int fu=find(uu),fv=find(vv);
		if(fu!=fv)
		{
			ans=ww;
			fa[vv]=uu;
			num++;
			if(num==n-1)break;
		}
	}
}

int main(){
	read(n),read(m);
	for(int i=1,u,v,w;i<=m;i++)
	{
		read(u),read(v),read(w);
		add(u,v,w);
	}

	kruskal();

	printf("%d %d\n",n-1,ans);
	return 0;
}

2021/6/18 07:06
加载中...