P1195 口袋的天空
  • 板块学术版
  • 楼主cyc120209
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/11/22 19:40
  • 上次更新2024/11/22 21:23:00
查看原帖
P1195 口袋的天空
1273193
cyc120209楼主2024/11/22 19:40

MLE了……

//***AC*** Orz ←给我AC
#include<bits/stdc++.h>

#define ll long long
#define endl "\n"

using namespace std;
const int maxn=2e5+10;

struct node{
	int x;
	int y;
	int s;
}a[maxn];

int father[maxn];
int n,m,k;

int Get_Father(int x){
	if(father[x]==x){
		return x;
	}
	
	int New_Father=Get_Father(x);
	father[x]=New_Father;
	return father[x];
}

void Add_Merge(int x,int y){
	int Xfather=Get_Father(x);
	int Yfather=Get_Father(y);
	
	if(Xfather!=Yfather){
		father[Xfather]=Yfather;
	}
}

void clear(int n){
	for(int i=0;i<=n;i++){
		father[i]=i;
	}
}

bool cmp(node a,node b){
	return a.s<b.s;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>m>>k;
	clear(n);
	
	for(int i=1;i<=m;i++){
		cin>>a[i].x>>a[i].y;
		cin>>a[i].s;
	}
	
	sort(a+1,a+1+m,cmp);
	
	int ans=-114514,cnt=0;
	bool flag=false;
	for(int i=1;i<=m;i++){
		int Xfather=Get_Father(a[i].x);
		int Yfather=Get_Father(a[i].y);
		
		if(Xfather!=Yfather){
			Add_Merge(a[i].x,a[i].y);
			
			cnt++;
			ans+=a[i].s;
		}
		
		if(cnt==n-k){
			flag=true;
			break;
		}
	}
	
	if(!flag){
		cout<<"No Answer"<<endl;
	}
	else cout<<ans<<endl;
	
	return 0;
}

求大佬帮!急

2024/11/22 19:40
加载中...