if you WA#11#12 and earn 86 pts by K

本人使用Kruskal算法 请尝试观察如下代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
const int maxm=2e5+7;

int fa[maxn];
int sz[maxn];

void set_make(int len)
{
    for(int i=1;i<=len;i++)
    {
        fa[i]=i;
        sz[i]=1;
    }
}

struct edge
{
    int a;
    int b;
    int c;
};

edge edges[maxm];

bool operator <(edge x,edge y)
{
    if(x.c<y.c)return true;
    else return false;
}

int find(int n)
{
    if(fa[n]==n)return fa[n];
    else return fa[n]=find(fa[n]);
}

bool merge(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return false;
    else
    {
        if(sz[x]>sz[y])swap(x,y);
        fa[x]=y;
        sz[y]+=sz[x];
        return true;
    }
}

bool check(int len)
{
    int cnt=0;
    for(int i=1;i<=len;i++)
    {
        if(fa[i]==i)
        {
            cnt++;
            if(cnt>1)return false;
        }
    }
    return true;
}

int main()
{
    int n=0,m=0,res=0;
    cin>>n>>m;
    set_make(n);
    for(int i=1;i<=m;i++)
    {
        cin>>edges[i].a>>edges[i].b>>edges[i].c;
    }
    sort(edges,edges+m+1);
    for(int i=1;i<=m;i++)
    {
        if(m==1)cout<<edges[1].c;
        if(check(n)==true)
        {
            cout<<res;
            return 0;
        }
        if(merge(edges[i].a,edges[i].b)==false)
        {
            //cout<<"DON'T"<<endl;
            continue;
        }
        else
        {
            //cout<<"Add edge between "<<edges[i].a<<' '<<" and "<<edges[i].b<<endl;
            res+=edges[i].c;
        }
    }
    cout<<"orz";
    return 0;
}

现在下面给出核心改正部分：

else
        {
            //cout<<"Add edge between "<<edges[i].a<<' '<<" and "<<edges[i].b<<endl;
            res+=edges[i].c;
            n--;
            //cout<<"Now there are "<<n<<" sets"<<endl;
            if(n==1)
            {
                cout<<res;
                return 0;
            }
        }

与此同时，原 bool check() 的检查部分注释掉，废弃不用。 检查 连通块 的位置务必注意，如本代码，当i>m时，将无法进入循环输出结果。 希望能帮助到有需要的人，共勉。