a[]的范围开大tle,开小re???

P3366 【模板】最小生成树

ljx979 @ 2024-10-17 12:06:08

include<bits/stdc++.h>
using namespace std;
int a[200005];
int ans=0;
int find(int a[],int i)
{
    while(i!=a[i])
        i=a[i];
    return i;
}
void ad(int a[],int x,int y)
{
    int r1=find(a,x);
    int r2=find(a,y);
    a[r2]=r1;
    return;
}
bool check(int a[],int x,int y)
{
    int r1=find(a,x);
    int r2=find(a,y);
    if(r1!=r2)
        return true;
    return false;
}
struct node
{
    int x,y,dis;
}e[100005];
bool cmp(const node a,const node b)
{
    return a.dis<b.dis;
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<=n;i++) a[i]=i;
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        e[i].x=x;
        e[i].y=y;
        e[i].dis=z;
    }
    sort(e,e+m,cmp);
    for(int i=0;i<m;i++)
    {
        int x=e[i].x;
        int y=e[i].y;
        if(check(a,x,y))
        {
//          cout<<x<<' '<<y<<' '<<e[i].dis<<endl;
            ans+=e[i].dis;
            ad(a,x,y);
        }
    }
    cout<<ans;
    return 0;
} 

by cly312 @ 2024-10-17 12:11:51

这是克鲁斯卡尔还是prim


by Zq_water @ 2024-10-17 12:13:33

@ljx979 您并查集的路径压缩呢


by Gcc_Gdb_7_8_1 @ 2024-10-17 12:19:14

@ljx979 跟 a 数组木有什么关系,主要如同上面的大佬所说,你 Kruskal 超时了。


by crz_qwq @ 2024-10-17 12:27:54

@ljx979 明显,你没有路径压缩


|