乱七八糟的求助

P3366 【模板】最小生成树

GODTREE @ 2022-11-03 10:53:30

#include <bits/stdc++.h>
using namespace std;
struct edge {
    int begin,end;
    int val;
};
bool cmp(edge a,edge b)
{
    if (a.val>b.val)
    {
        return false;
    }
    return true;
}
int main()
{
    int n,m;
    cin>>n>>m;
    edge edges[m+1],mintree[m-n+2];
    for (int i=1;i<=n;i++)//输入每条边 
    {
        cin>>edges[i].begin>>edges[i].end>>edges[i].val;
    }
    sort(edges+1,edges+n+1,cmp);//排序所有边 
    mintree[1]=edges[1];//一条边必然为树 
    int sum=1,r=1;
    while (sum<m-n+1)//当边数构成一棵树时结束循环 
    {
        bool flag1=true;
        while (flag1)
        {
            bool flag2=true;
            for (int i=1;i<=sum;i++)
            {
                if (mintree[i].begin==edges[r+1].begin||mintree[i].begin==edges[r+1].end||mintree[i].end==edges[r+1].end||mintree[i].end==edges[r+1].begin)
                {
                    flag2=false;
                    r++;
                    break;
                }
            }
            if (flag2)
            {
                sum++;
                mintree[sum]=edges[r];
                flag1=false;
            }
        }
    }
    sum=0;
    for (int i=1;i<=sum<m-n+1;i++)
    {
        sum+=mintree[i].val;
    }
    cout<<sum;
    return 0;
}

by Rosaya @ 2022-11-03 11:02:20

cmp 写挂了,把 > 改成 >= 。


by GODTREE @ 2022-11-05 21:19:00

@Dark_night_qwq thank you


|