求助,KruskalWA两个点,86分
查看原帖
求助,KruskalWA两个点,86分
576242
StkOvflow楼主2022/8/29 08:41
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+10, INF = 0x3f3f3f3f;
int p[N * 2], n, m;

struct Edge
{
    int a,b,w;
}edge[N];

bool cmp(Edge x,Edge y)
{
    return x.w < y.w;
}

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int krus()
{
    sort(edge, edge + m, cmp);
    
    int res = 0,cnt = 0;
    
    for(int i = 0;i < m;i ++ )
    {
        int a = find(edge[i].a);
        int b = find(edge[i].b);
        int w = edge[i].w;
        if(a != b)
        {
            cnt ++;
            res += w;
            p[a] = b;
            if(cnt == n - 1) break;
        }
    }
    
    if(cnt < n - 1) return INF;
    else return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    cin >> n >> m;
    
    for(int i = 0;i < m;i ++ ) p[i] = i;
    
    for(int i = 0;i < m;i ++ )
    {
        int a,b,w;
        cin >> a >> b >> w;
        edge[i] = {a,b,w};
    }
    
    int t = krus();
    
    if(t == INF) puts("orz");
    else cout << t << endl;
    
    return 0;
}

大佬帮忙调一下,11和12 WA了

2022/8/29 08:41
加载中...