蒟蒻刚学1小时OI，求调最小生成树

To_2051 @ 2024-03-24 17:38:32

#include<bits/stdc++.h>
using namespace std;
int ans,n,m,cnt;
struct node{
    int u,v,w;
}a[100001];
int fa[100001];
bool cmp(node a,node b)
{
    return a.w<b.w;
}
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
bool work()
{
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int eu=find(a[i].u),ev=find(a[i].v);
        if(eu==ev) continue;
        cnt++;ans+=a[i].w;
        fa[eu]=ev;
        if(cnt==n) 
        {
            cout<<"orz";
            return 0;
        }
    }
    return 1;
}
int main()
{
    int pos;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        pos++;
        cin>>a[pos].u>>a[pos].v>>a[pos].w;
    }
    sort(a+1,a+m+1,cmp);
    if(work()) cout<<ans;
    return 0;
}

by lalaouye @ 2024-03-24 17:57:05

@To_2051

#include<bits/stdc++.h>
using namespace std;
int ans,n,m,cnt;
struct node{
    int u,v,w;
}a[200001];
int fa[100001];
bool cmp(node a,node b)
{
    return a.w<b.w;
}
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
bool work()
{
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int eu=find(a[i].u),ev=find(a[i].v);
        if(eu==ev) continue;
        cnt++;
        ans+=a[i].w;
        fa[eu]=ev;
    }
    if (cnt < n - 1)
    {
        puts ("orz");
        return 0;
    }
    return 1;
}
int main()
{
    int pos;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        pos++;
        cin>>a[i].u>>a[i].v>>a[i].w;
    }
    sort(a+1,a+m+1,cmp);
    if(work()) cout<<ans;
    return 0;
}

1.无解判错

2.数组开小

by Melo_DDD @ 2024-03-24 17:59:42

@To_2051

A了：

#include<bits/stdc++.h>
using namespace std;
int ans,n,m,cnt;
struct node{
    int u,v,w;
}a[200001];
int fa[200001];
bool cmp(node a,node b)
{
    return a.w<b.w;
}
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
bool work()
{
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int eu=find(a[i].u),ev=find(a[i].v);
        if(eu==ev) continue;
        cnt++;ans+=a[i].w;
        fa[eu]=ev;
        if(cnt==n - 1) 
        {
            return 1;
        }
    }
    cout << "orz" <<'\n';
    return 0;
}
int main()
{
    int pos = 0;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        pos++;
        cin>>a[pos].u>>a[pos].v>>a[pos].w;
    }
    sort(a+1,a+pos+1,cmp);
    if(work()) cout<<ans<< endl;
    return 0;
}

首先，数组开小了。

其次，cnt判断条件是==n - 1 而不是==n，因为树是n个点n - 1条边的连通图，所以边数达到n - 1时就连通了。

最后，函数返回值写反了，cnt==n-1是连通所以返回1，否则不连通输出orz返回0

麻烦关注

by To_2051 @ 2024-03-24 17:59:52

@lalaouye 已关,%%%

by To_2051 @ 2024-03-24 18:00:46

@shin_chan_jiang orz