c语言最小生成树问题(街道管道铺设问题)

Question

点和边的数量，及边之间的关系已经给定了。
只需要输入题中各边的的赋权值。
输入格式要以"("左括号开始，数据间用逗号隔开，以右括号结束

Answer 1

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1e5+10;
int par[105];
struct node{
    int from,to,cost;
}no[maxn*4];
void init()
{
    for(int i=0;i<maxn;i++)
        par[i]=i;
}
int find(int x)
{
    return par[x]==x?x:par[x]=find(par[x]);
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
    par[x]=y;
}
bool same(int x,int y)
{
    return find(x)==find(y);
}
int n,m,mo;
bool cmp(node x,node y)
{
    return x.cost<y.cost;
}

int kruskal()
{
    int sum=0;
    for(int i=0;i<m;i++)
    {
        node a=no[i];
        if(!same(a.from,a.to)){
            unite(a.from,a.to);
            sum+=a.cost;
        }
    }
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>mo>>m>>n)
    {
        init();
        for(int i=0;i<m;i++)
        {
            cin>>no[i].from>>no[i].to>>no[i].cost;
        }
        sort(no,no+m,cmp);
        int p=kruskal();
        if(p<=mo)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}