求助.全WA了
查看原帖
求助.全WA了
238768
Forest_楼主2020/11/6 11:42
#include <bits/stdc++.h>
using namespace std;
const int maxn=5005;
int n,m;
struct edge{
	int u,v,w;
}e[200005];
vector <int> g[maxn];
int s[maxn],head[maxn];
bool cmd(edge x,edge y){return x.w<y.w;};
int find(int x){if(x!=head[x]) head[x]=find(head[x]);return head[x];}
void dfs(int r){s[r]=1;int kk=g [r].size();for(int i=0;i<kk;i++)if(s[g[r][i]]==0) dfs(g[r][i]);}
int kruskal()
{
	int ans=0;
	for(int i=1;i<=n;i++) head[i]=i;
	sort(e+1,e+m+1,cmd);
	for(int i=1;i<=m;i++)
	{
		int u=e[i].u,v=e[i].v,w=e[i].w;
		int aa=find(u),bb=find(v);
		if(aa==bb) continue;
		head[v]=u;
		ans+=w;
	}
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[u].push_back(v);g[v].push_back(u);
		e[i].u=u;e[i].v=v;e[i].w=w;
	}
	dfs(1);
	for(int i=1;i<=n;i++)
	{
		if(s[i]==0)
		{
			puts("orz");
			return 0;
		}
	}
	printf("%d",kruskal());
	
	return 0;
}
2020/11/6 11:42
加载中...