题目背景
小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。
有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。
题目描述
给你云朵的个数 N，再给你 M 个关系，表示哪些云朵可以连在一起。
现在小杉要把所有云朵连成 K 个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。
输入格式
第一行有三个数 N,M,K。
接下来 M 行每行三个数 X,Y,L，表示 X 云和 Y 云可以通过 L 的代价连在一起。
输出格式
对每组数据输出一行，仅有一个整数，表示最小的代价。
如果怎么连都连不出 K 个棉花糖，请输出 No Answer。
输入输出样例
输入 #1
3 1 2
1 2 1输出 #1
1说明/提示
对于 30% 的数据，1≤N≤100，1≤M≤10^3；
对于 100% 的数据，1≤N≤10^3，1≤M≤10^4，1≤K≤10，1≤X,Y≤N，0≤L<10^4。
解析：因为某些云朵是不能相连的，因此会产生若干个连通块，题目要求K个，我们发现，一个连通块以最小生成树相连，每删除一条边，那么会独立一个点，独自成为一个连通块，因此若初始连通块个数已经大于K或者n<k，那么肯定就无解了，否则我们可以每次删一条边以增加一个连通块，从而达到K个。
做法:每个连通块内部求一个最小生成树，存下树边，最后需要补充x个联通块，那么就从所用树边里从大到小删除x个，这样就是最小代价。
#include <bits/stdc++.h>
using namespace std;
const int N=2e4+5;
typedef pair<int,int> PII;
int n,m,k,cnt,ans;//cnt记录连通块的个数
vector<int> v[N];
bool vis[N];//判断是否访问过
map<PII,int> w;//记录两点间的权值
int f[N];
int find(int x)
{if(f[x]!=x) f[x]=find(f[x]);return f[x];
}
struct node
{int x,y,w;bool operator<(const node&p) const{return w<p.w;}
}tr[N];
vector<int> mx;//记录所有存下来的边
void go(int nod)
{cnt++;queue<int> q;q.push(nod);int num=0;//记录当前连通块的边数vis[nod]=true;vector<int> has;//当前所在连通块包含的点has.push_back(nod);while(q.size()){int u=q.front();q.pop();for(int i=0;i<v[u].size();i++){int j=v[u][i];if(!vis[j]){vis[j]=true;has.push_back(j);q.push(j);}}}//求一次最小生成树for(int i=0;i<has.size();i++){int u=has[i];for(int j=0;j<v[u].size();j++){int p=v[u][j];tr[++num]={u,p,w[{u,p}]};}}sort(tr+1,tr+num+1);for(int i=1;i<=num;i++){int x=tr[i].x,y=tr[i].y,value=tr[i].w;x=find(x),y=find(y);if(x!=y){f[x]=y;ans+=value;mx.push_back(value);}}
}
void solve()
{scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++) f[i]=i;for(int i=1;i<=m;i++){int x,y,value;scanf("%d%d%d",&x,&y,&value);v[x].push_back(y);v[y].push_back(x);if(!w[{x,y}]) w[{x,y}]=w[{y,x}]=value;//存储两点最小的一条边else w[{x,y}]=w[{y,x}]=min(w[{x,y}],value);}for(int i=1;i<=n;i++) if(!vis[i]) go(i);if(cnt>k||n<k){printf("No Answer\n");//连通块个数大于k必然就是无解了return;}sort(mx.begin(), mx.end());//按权值排个序k-=cnt;//还需要几块for(int i=mx.size()-1;i>=0&&k>0;i--,k--) ans-=mx[i];printf("%d\n",ans);
}
int main()
{int t=1;//scanf("%d",&t);while(t--) solve();return 0;
}
