https://www.luogu.com.cn/problem/P1195

#include<cstdio>
#include<algorithm>
using namespace std;
const int n = 1001;
const int m = 10001;
int ans = 0;
struct Edge
{
? ?int u,v,w;
};
Edge E[m];
int ?father[n];
void Init_father()
{
? ?for(int i=1;i<=n;i++)
? ?{
? ? ? ?father[i]=i;
? ?}
}
bool comp(Edge lhs,Edge rhs)
{
? ?if(lhs.w<rhs.w)
? ? ? ?return true;
? ?else
? ? ? ?return false;
}
int find(int x)
{
? ?while(x != father[x])
? ?{
? ? ? ?x = father[x];
? ?}
? ?return x;
}
int main()
{
? ?int N,M,K;//N為云朵數(shù)目，M為關(guān)系數(shù)目，K為棉花糖數(shù)目
? ?scanf("%d%d%d",&N,&M,&K);
? ?for(int i=1;i<=M;i++)
? ?{
? ? ? ?scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
? ?}
? ?Init_father();
? ?sort(E+1,E+1+M,comp);
? ?for(int i=1;i<=M;i++)
? ?{
? ? ? ?int countaaa = 0;
? ? ? ?//遍歷每一條邊
? ? ? ?int father_u=find(E[i].u);
? ? ? ?int father_v=find(E[i].v);
? ? ? ?if(father_u != father_v)
? ? ? ?{
? ? ? ? ? ?//Union操作
? ? ? ? ? ?father[father_u]=father_v;
? ? ? ? ? ?ans = ans + E[i].w;//不在一個(gè)集合中則加入這條邊且權(quán)值增加
? ? ? ?}
? ? ? //統(tǒng)計(jì)此時(shí)有幾個(gè)集合了
? ? ? for(int j=1;j<=N;j++)
? ? ? {
? ? ? ? ? if(father[j] == j)
? ? ? ? ? {
? ? ? ? ? ? ? countaaa++;
? ? ? ? ? }
? ? ? }
? ? ? if(countaaa == K)
? ? ? {
? ? ? ? ? //達(dá)到了K個(gè)集合
? ? ? ? ? printf("%d",ans);
? ? ? ? ? return 0;//達(dá)到K個(gè)集合則停止循環(huán),注意要使用return語(yǔ)句而不是break，使用break之后后面NA也會(huì)被輸出
? ? ? }
? ?}
? ?//循環(huán)完畢都沒有達(dá)到K個(gè)集合
? ?printf("No Answer");
}