社区讨论

Kruskal WA 3点

P3366【模板】最小生成树参与者 2已保存回复 2

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@mi6hbahh
此快照首次捕获于
2025/11/20 04:52
4 个月前
此快照最后确认于
2025/11/20 04:52
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
#define MAXM 401000
struct bian
{
    int x,y,l;    
};
bian a[MAXM];
int f[MAXM],n,m;
bool cmp(bian a,bian b)
{
    return a.l<b.l;
}
int zhao(int x)
{
    if(x == f[x])
        return x;
    return f[x] = zhao(f[x]);
}
void he(int x,int y)
{
    int fx=zhao(x);
    int fy=zhao(y);
    f[fy] = fx;
}
void rd()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].l);
    }
    for(int i=1;i<=n;i++)
        f[i] = i;
}
int main()
{
    rd();
    sort(a+1,a+m+1,cmp);
    int s = 0,ans = 0;
    for(int i=1;i<=m;i++)
    {
        if(zhao(a[i].x)!=zhao(a[i].y))
        {
            ans += a[i].l;
            s++;
            he(a[i].x,a[i].y);
        }
        if(s == n-1)
            break;
    }
    if(s < n-1)
        cout<<"orz";
    else
        cout<<ans<<endl;
    return 0;
}
/* 5 5 1 2 1 1 3 1 2 3 2 1 5 5 4 5 3 1 4 6 */

回复

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

正在加载回复...