传送门：https://www.nowcoder.net/acm/contest/76/B
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld
题目描述
随着如今社会的不断变化，交通问题也变得越来越重要，所以市长决定建设一些公路来方便各个城市之间的贸易和交易。虽然市长的想法很好，但是他也遇到了一般人也经常头疼的问题，那就是手头的经费有限……在规划过程中，设计师们已经预算出部分城市之间建设公路的经费需求。现在市长想知道，它能不能将他的m个城市在有限的经费内实现公路交通。如果可以的话，输出Yes，否则输出No（两个城市不一定要直接的公路相连，间接公路到达也可以。）
输入描述:
测试输入包含多条测试数据
每个测试数据的第1行分别给出可用的经费c(<1000000)，道路数目n(n<10000)，以及城市数目m(<100)。
接下来的n行给出建立公路的成本信息，每行给出三个整数，分别是相连的两个城市v1、v2(0<v1,v2<=m)以及建设公路所需的成本h(h<100)。
输出描述:
对每个测试用例，输出Yes或No。
输入例子:
20 10 5
1 2 6
1 3 3
1 4 4
1 5 5
2 3 7
2 4 7
2 5 8
3 4 6
3 5 9
4 5 2
输出例子:
Yes
-->
示例1
输入
20 10 5
1 2 6
1 3 3
1 4 4
1 5 5
2 3 7
2 4 7
2 5 8
3 4 6
3 5 9
4 5 2
输出
Yes
示例2
输入
10 2 2
1 2 5
1 2 15
输出
Yes
备注:
两个城市之间可能存在多条线路 思路：最小生成树，用的是Kruskal算法，即对边的权值从小到大排序，然后再用并查集维护边的关系。在加边的时，可以在边的总费用超过输入的预计费用直接return。
#include<cstring>
#include<string>
#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int pre[];
int n,m,c;
int fid(int x){
return pre[x] == x? x:pre[x] = fid(pre[x]);
}
void join(int x,int y){
int dx = fid(x),dy = fid(y);
if(dx != dy){
pre[dx] = dy;
}
}
struct note{
int u,v,cost;
}p[];
bool cmp(note x,note y){
return x.cost < y.cost;
}
int solve(){
int ans = ;
int sum = ;
sort(p,p+m,cmp);
for(int i = ; i < m ; i++){
if(fid(p[i].u) != fid(p[i].v)){
++ans;
sum += p[i].cost;
}
if(sum > c)return ;
if(ans == n)return ;
}
return ;
}
int main(){
while(~scanf("%d %d %d",&c,&m,&n)){
for(int i = ; i <= n ; i++) pre[i] = i;
for(int i = ; i < m ; i ++){
scanf("%d %d %d",&p[i].u,&p[i].v,&p[i].cost);
}
solve()?puts("Yes"):puts("No");
}
}