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