道路建设

链接：https://ac.nowcoder.com/acm/problem/15108

题目描述：

随着如今社会的不断变化，交通问题也变得越来越重要，所以市长决定建设一些公路来方便各个城市之间的贸易和交易。虽然市长的想法很好，但是他也遇到了一般人也经常头疼的问题，那就是手头的经费有限……在规划过程中，设计师们已经预算出部分城市之间建设公路的经费需求。现在市长想知道，它能不能将他的m个城市在有限的经费内实现公路交通。如果可以的话，输出Yes，否则输出No（两个城市不一定要直接的公路相连，间接公路到达也可以。）

输入描述：

测试输入包含多条测试数据
每个测试数据的第1行分别给出可用的经费c(<1000000)，道路数目n(n<10000)，以及城市数目m(<100)。
接下来的n行给出建立公路的成本信息，每行给出三个整数，分别是相连的两个城市v1、v2(0<v1,v2<=m)以及建设公路所需的成本h(h<100)。

输出描述：

对每个测试用例，输出Yes或No。

solution：

最小生成树，将边的信息通过结构体存储起来，并将结构体按照公路成本从小到大排序，从小到大取出边的信息，如果两个点已经可以到达了，那么就跳过此次循环，如果不能到达，就将这条路建造，并且加上造路所需的花费。比较最终将所有城市连接起来的花费是否超出预支，以及所有城市间是否可相互到达

有点小瑕疵，没注意到是多条测试数据，不过已经可以ac了

#include<bits/stdc++.h>
using namespace std;
long long c,n,m,s=0;
struct num
{
    int u,v,h;
}e[10005];
int f[105];          
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
void union1(int x,int y)
{
    int u=find(x),v=find(y);
    f[v]=u;
}
bool cmp(struct num a,struct num b)
{
    return a.h<b.h;
}
void kruscal()
{
    for(int i=1;i<=m;i++)
        f[i]=i;
    sort(e,e+n,cmp);
    for(int i=0;i<n;i++)
    {
        if(find(e[i].u)!=find(e[i].v))
        {
            s+=e[i].h;
            union1(e[i].u,e[i].v);
        }
    }
}
int main()
{
    cin>>c>>n>>m;
    for(int i=0;i<n;i++)
        cin>>e[i].u>>e[i].v>>e[i].h;
    kruscal();
    if(s>c)cout<<"No";
    else 
    {
        int num=find(1);
        for(int i=2;i<=m;i++)
        {
            if(num!=find(i))
            {
                num=-1;
                break;
            }
        }
        if(num!=-1)
            cout<<"Yes";
        else
            cout<<"No";
    }
}