求助,为什么会WA,请问一下
查看原帖
求助,为什么会WA,请问一下
525998
huangjiasheng楼主2022/11/14 21:51
/*****************************************
备注:
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e7 + 10;
const int INF = 0x3f3f3f3f;
int a[N],n,m;
struct node
{
	int x,y,z;
}edg[N];
void init()
{
	for(int i=0;i<=n;i++)
		a[i]=i;
}
bool cmp(node a,node b)
{
	return a.z<b.z;
}
int find(int x)
{
	if(x==a[x]) 
		return x;
	return a[x]=find(a[x]);
}
void kruskal()
{
	init();
	int ans=0;
	int cnt=0;
	for(int i=1;i<=m;i++)
	{
		int x=find(edg[i].x);
		int y=find(edg[i].y);
		if(x!=y)
		{
			ans+=edg[i].z;
			a[x]=y;
			cnt++;
			if(cnt==n-1)
				break;
		}
	}
	if(cnt==n-1) 
		cout <<ans;
	else 	
		cout << "orz";
} 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>edg[i].x>>edg[i].y>>edg[i].z;
	sort(edg+1,edg+1+m,cmp);
	kruskal();
	return 0;
}

2022/11/14 21:51
加载中...