求大佬,我wa了三个点,都是误判成orz的,但不知为何
查看原帖
求大佬,我wa了三个点,都是误判成orz的,但不知为何
136992
ClearDream15楼主2020/10/18 19:29
#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
struct Edge{
	ll to;
	ll next;
	ll w;
	bool operator<(Edge&other) const{
		return w<other.w;
	}
};
Edge graph[100005];
ll n,m;
ll mst=0;
ll root[500005];
ll found(ll a){
	if(root[a]==a) return a;
	else return root[a] = found(root[a]);
}
void merge(ll a,ll b){
	root[found(a)] = found(root[b]);
}
bool Kruskal(){
	for(int i = 1;i<=n;i++){
		root[i] = i;
	}
	ll count = 0;
	mst = 0;
	sort(graph+1,graph+1+m);
	for(int i = 1;i<=m;i++){
		ll x = graph[i].to;
		ll y = graph[i].next;
		ll w = graph[i].w;
		if(found(x)!=found(y)){
			merge(x,y);
			mst+=w;
			count++;
			if(count == n-1) return true;
		}
	} 
	return false;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i = 1;i<=m;i++){
		scanf("%lld%lld%lld",&graph[i].to,&graph[i].next,&graph[i].w);
	}
	if(Kruskal()){
		printf("%lld",mst);
	}
	else printf("orz");
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

2020/10/18 19:29
加载中...