道路建设

最小生成树问题；
选n-1条边；

#include<bits/stdc++.h>
using namespace std;
//因为给边了，所以用最小生成树
const int maxn=10100;
int n,m,c,sum=0,f[maxn];
struct e{
    int u,v,w;
}edge[2*maxn];
int find(int x)
{
    if(x==f[x]) return x;
    else return f[x]=find(f[x]);
}
bool cmp(e i,e j)
{
    return i.w<j.w;
}
void krusal()
{
    for(int i=1;i<=n;i++)
    {
        int cnt=0,eu=find(edge[i].u),ev=find(edge[i].v);
        if(eu!=ev)
        {
            f[eu]=ev;
            sum+=edge[i].w;
            cnt++;
        }
        if(cnt==n-1) return;
    }
}
int main()
{
    while(scanf("%d %d %d",&c,&n,&m)!=EOF)
    {
        sum=0;
        memset(edge,0,sizeof(edge));
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++) f[i]=i;
        for(int i=1;i<=n;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            edge[i].u=u,edge[i].v=v,edge[i].w=w;
        }
        sort(edge+1,edge+1+n,cmp);
        krusal();
        if(sum<=c) printf("Yes\n");//如果花费小于所给经费，则满足
        else printf("No\n");
    }
}