Kruskal 79 #8#9#10 MLE 求调

MLE

$Code$

//【模板】最小生成树
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc() getchar()
#define pc(x) putchar(x)
typedef string str;
il int re(){int s=0;bool w=0;char c=gc();while(!isdigit(c)){if(c=='-')w=1;c=gc();}while(isdigit(c))s=(s<<1)+(s<<3)+c-48,c=gc();return w?-s:s;}
template<typename T>
il void p(T x){if(x<0)pc('-'),x=-x;if(x>9)p(x/10);pc(x%10+48);return;}
il void ps(str x){int l=x.length(),i=0;for(;i<l;i++)pc(x[i]);return;}

int n,m;
const int N=5010,M=20010;//点数max,边数max
struct Union_Find//并查集
{
	int fa[N]={0};
	il void init()//并查集初始化
	{
		for(int i=1;i<=n;i++)
			fa[i]=i;
		return;
	}
	il int getroot(int x)//找最大祖先
	{
		return x==fa[x]?x:fa[x]=getroot(fa[x]);
	}
	il bool merge(int x,int y)//合并,成功返回1,失败返回0
	{
		x=getroot(x),y=getroot(y);
		if(x==y)
			return 0;
		fa[y]=x;
		return 1;
	}
};
struct Kruskal//最小生成树
{
	struct edge
	{
		int u,v,w;
		il bool operator <(const edge &x) const
		{
			return w<x.w;
		}
	}e[M];
	Union_Find Uf;//并查集
	int tot=0,ans=0;//已经选了多少条边
	il void kruskal()
	{
		sort(e+1,e+m+1);
		for(int i=1;i<=m;i++)
			if(Uf.merge(e[i].u,e[i].v))
			{
				ans+=e[i].w;
				tot++;
				if(tot==n-1)
					break;
			}
		return;
	}
}K;
int main()
{
	n=re(),m=re();
	K.Uf.init();
	for(int i=1;i<=m;i++)
		K.e[i].u=re(),K.e[i].v=re(),K.e[i].w=re();
	K.kruskal();
	if(K.Uf.getroot(1)!=K.Uf.getroot(n))
		ps("orz");
	else
		p(K.ans);
	return 0;
}