求助!急

P3366 【模板】最小生成树

Jerry_Money @ 2024-08-03 14:21:39

#include<bits/stdc++.h>
using namespace std;
int t;
int n,m;
struct sb{
    int x,y,z;
}e[200086];
bool cnm(sb x,sb y){
    return x.z<y.z;
}
int f[100086];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>e[i].x>>e[i].y>>e[i].z;
    }
    sort(e+1,e+1+m,cnm);
    for(int i=1;i<=n;i++)f[i]=i;
    int ans=0;
    int tot=0;
    for(int i=1;i<=m;i++){
        tot++;
        if(find(e[tot].x)==find(e[tot].y)){
            continue;
        }
        ans+=e[tot].z;
        f[find(e[tot].y)]=find(e[tot].x);

        if(tot==n-1){
            cout<<ans;
            return 0;
        }
    }
    cout<<"org";
}

by Pink_Cut_Tree @ 2024-08-03 14:26:01

@Jerry_Money 不是 orz 吗你输了个 org


by tianyun4188 @ 2024-08-03 14:26:34

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,ans;
struct node
{
    int f,t,d;
}a[200005];//存边,Kruskal不用建图
bool cmp(node x,node y){return x.d<y.d;}
struct bin
{
    int w[5005];
    int find(int x)
    {
        if(x==w[x]) return x;
        w[x]=find(w[x]);
        return w[x];
    }
    void add(int x,int y)
    {
        w[find(x)]=find(y);
        return ;
    }
    bool ask(int x,int y)
    {
        if(find(x)==find(y)) return true;
        else return false;
    }
}b;//并查集
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].f,&a[i].t,&a[i].d);
    for(int i=1;i<=n;i++) b.w[i]=i;//并查集初始化
    sort(a+1,a+m+1,cmp);//按边权排序
    for(int i=1;i<=m;i++)//枚举每条边
    {
        if(b.ask(a[i].f,a[i].t)) continue;//连通则跳过
        ans+=a[i].d;//否则记录
        b.add(a[i].f,a[i].t);//改为连通
    }
    for(int i=2;i<=n;i++)
        if(!b.ask(1,n))
        {
            printf("orz");
            return 0;
        }//判断是否连通
    printf("%d",ans);
    return 0;
}

本人已过,拿去用吧 不信? ·-看这里


by qazsedcrfvgyhnujijn @ 2024-08-03 14:26:47

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 5003, M = 2e5 + 3;
struct DSU {
    int fa[N], siz[N];
    void init(int n = N - 1) { for (int i = 0; i <= n; ++i) fa[i] = i, siz[i] = 1; }
    int find(int k) { return fa[k] == k ? k : fa[k] = find(fa[k]); }
    void merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;
        if (siz[u] < siz[v]) swap(u, v);
        fa[v] = u, siz[u] += siz[v];
    }
    bool query(int u, int v) { return find(u) == find(v); }
} dsu;
struct Edge {
    int from, to, val;
    Edge(int u = 0, int v = 0, int w = 0) : from(u), to(v), val(w) {}
    bool operator < (const Edge &other) const { return val < other.val; }
} e[M];
int n, m, ans;

signed main() {
    cin >> n >> m;
    dsu.init(n);
    for (int i = 1; i <= m; ++i)
        cin >> e[i].from >> e[i].to >> e[i].val;
    sort(e + 1, e + 1 + m);
    for (int i = 1; i <= m; ++i)
        if (dsu.query(e[i].from, e[i].to) == 0)
            dsu.merge(e[i].from, e[i].to), ans += e[i].val;
    for (int i = 2; i <= n; ++i)
        if (dsu.query(1, i) == 0)
            return cout << "orz" << '\n', 0;
    cout << ans << '\n';

    return 0;
}

还有不要在代码里加文明用语,Luogu 容易被封号,CSP 和 NOI(p) 容易被禁赛。


by tianyun4188 @ 2024-08-03 14:29:00

来我团吧!这里的资源很多,可以和我一起建设,团主(我awa)虽然是个蒟蒻,但是我会努力刷题的qwq!-加入看这里


by Jerry_Money @ 2024-08-03 14:31:10

感谢大佬们


by tianyun4188 @ 2024-08-03 14:34:10

@Jerry_Money 来我团吧谢谢!我们可以一起找题!我团非常宠人的招人中谢谢!-加入吧谢谢!!!!!!


|