orz怎么调

Al_Ahmar @ 2022-07-24 19:30:01

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data,v1,v2; 
}ns[200005];
int n,m,v1,v2,f[200005];
long long ans;
bool cmp(node x,node y)
{
    return x.data<y.data;
}
int find(int x)
{
    if(f[x]==x)
    {
        return x;
    }
    else
    {
        f[x]=find(f[x]);
        return f[x];
    }
}
void merge(int v1,int v2)
{
    int fx=find(v1);
    int fy=find(v2);
    if(fx!=fy)
    {
        f[fx]=fy;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>ns[i].v1>>ns[i].v2>>ns[i].data;
    }
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
    }
    sort(ns+1,ns+m+1,cmp);
    int cnt=0;
    for(int i=1;i<=m;i++)
    {
        v1=ns[i].v1;
        v2=ns[i].v2;
        if(find(v1)!=find(v2))
        {
            merge(v1,v2);
            ans+=ns[i].data;
            cnt++;
        }
        if(cnt==n-1)
        {
            break;
        }
    }
    cout<<ans;
    return 0;
}

by Resolute_Faith @ 2022-07-24 19:31:58

cnt不等于n-1

by qnqfff @ 2022-07-24 19:42:28

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data,v1,v2; 
}ns[200005];
int n,m,v1,v2,f[200005];
long long ans;
bool cmp(node x,node y)
{
    return x.data<y.data;
}
int find(int x)
{
    if(f[x]==x)
    {
        return x;
    }
    else
    {
        f[x]=find(f[x]);
        return f[x];
    }
}
void merge(int v1,int v2)
{
    int fx=find(v1);
    int fy=find(v2);
    if(fx!=fy)
    {
        f[fx]=fy;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>ns[i].v1>>ns[i].v2>>ns[i].data;
    }
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
    }
    sort(ns+1,ns+m+1,cmp);
    int cnt=0;
    for(int i=1;i<=m;i++)
    {
        v1=ns[i].v1;
        v2=ns[i].v2;
        if(find(v1)!=find(v2))
        {
            merge(v1,v2);
            ans+=ns[i].data;
            cnt++;
        }
        if(cnt==n-1)
        {
            cout<<ans;
            return 0;
        }
    }
    cout<<"orz";
    return 0;
}

by Al_Ahmar @ 2022-07-24 22:04:52

@qnqfff thk