社区讨论

感觉没问题可就是过不了

P1195口袋的天空参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m090qvyo
此快照首次捕获于
2024/08/25 11:37
去年
此快照最后确认于
2024/08/25 11:53
去年
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
struct yun
{
    int x;
    int y;
    int dis;
};
int find(int x,int fa[])
{
    if (x==fa[x])
    {
        return x;
    }
	return fa[x]=find(fa[x],fa);
}
bool bj(yun a,yun b)
{
	return a.dis<b.dis;
}
int main()
{
    yun a[200005];
    int fa[200005]={0};
    int n=0;
    int m=0;
    int k=0;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].dis;
    }
    for(int i=1;i<=m;i++)
    {
        fa[i]=i;
    }
    int ans=0;
    int b=0;
    sort((a+1),(a+m+1),bj);
    for(int i=1;i<=m;i++)
    {
        if(find(a[i].x,fa)!=find(a[i].y,fa))
        {
            fa[find(a[i].x,fa)]=find(a[i].x,fa);
            ans+=a[i].dis;
            b++;
        }
        if(b>=n-k)
        {
            break;
        }
    }
    if(b>=n-k)
    {
        cout<<(ans)<<endl;
    }
    else
    {
        cout<<"No Answer"<<endl;
    }
    return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...