道路建设题解

最小生成树裸题，注意同一个u到v可能有多个w，所以要取最小的那一条边。最后比较最小生成树的值与C的大小，判断是否能建设成道路，下面给出prim解法

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int g[N][N];
int dis[N];
bool vis[N];
int c,n,m;
int prim()
{
    int ans=0;
    dis[1]=0;
    for(int i=1;i<=m;i++)
    {
        int t=-1;
        for(int j=1;j<=m;j++)
        {
            if(!vis[j]&&(t==-1||(dis[t]>dis[j])))
               t=j;
        }
        ans+=dis[t];
        vis[t]=1;
        for(int j=1;j<=m;j++)
        {
            dis[j]=min(dis[j],g[t][j]);
        }
    }
    return ans;
}
int main()
{
    while(scanf("%d%d%d",&c,&n,&m)!=EOF)
    {
        memset(g,0x3f,sizeof(g));
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        while(n--)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            g[u][v]=g[v][u]=min(g[u][v],min(g[v][u],w));
        }
        if(c>=prim()) printf("Yes\n");
        else printf("No\n");
    }
}