为什么没有输出了？？？？？

Joseph_H @ 2021-12-30 15:41:15

#include<bits/stdc++.h>
using namespace std;
const int NUM = 5e3 + 1;
int s[NUM];
struct node{
    int u,v,w;
};
node f[200001];
int find(int u){
    return s[u] == 0 ? u : find(s[u]);
}
inline int read(){
    int now = 0,nev = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') nev = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        now = (now << 1) + (now << 3) + (c & 15);
        c = getchar();
    }
    return now * nev;
}
int n,m;
bool cmp(node a,node b){
    return a.w < b.w;
}
int kruskal(){
    int ans = 0;
    for(int i = 1;i <= n;i++){
        s[i] = i;
    }
    stable_sort(f + 1,f + m + 1,cmp);
    for(int i = 1;i <= m;i++){
        int b = find(f[i].u);
        int c = find(f[i].v);
        if(b == c) continue;
        s[c] = b;
        ans += f[i].w;
    }
    if(ans == 0){
        printf("orz");
    }
    printf("%d",ans);
}
int main(){
    n = read();
    m = read();
    for(int i = 1;i <= n * n;i++){
        f[i].w = 100000;
    }
    for(int i = 1;i <= m;i++){
        f[i].u = read();
        f[i].v = read();
        f[i].w = read();
    }
    kruskal();
}

by _NTT_ @ 2021-12-30 15:55:26

@Joseph_H find这么写

int find(int u){
    return s[u] = s[u] == u ? u : find(s[u]);
}

by Joseph_H @ 2021-12-30 15:58:21

谢谢

by Joseph_H @ 2021-12-30 16:06:54

为什么改了之后T3个wa1个？

#include<bits/stdc++.h>
using namespace std;
const int NUM = 5e3 + 1;
int s[NUM];
void look(){
    printf("what happen?\n");
}
struct node{
    int u,v,w;
    node(int _u,int _v,int _w){
        u = _u;
        v = _v;
        w = _w;
    }
};
vector <node> v;
int find(int u){
    return s[u] == u ? u : find(s[u]);
}
inline int read(){
    int now = 0,nev = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') nev = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        now = (now << 1) + (now << 3) + (c & 15);
        c = getchar();
    }
    return now * nev;
}
int n,m;
bool cmp(node a,node b){
    return a.w < b.w;
}
int kruskal(){
    int ans = 0;
    for(int i = 1;i <= n;i++){
        s[i] = i;
    }
    stable_sort(v.begin(),v.end(),cmp);
    for(int i = 0;i < m;i++){
        int b = find(v[i].u);
        int c = find(v[i].v);
        if(b == c) continue;
        s[c] = b;
        ans += v[i].w;
    }
    printf("%d",ans);
}
int main(){
    n = read();
    m = read();
    for(int i = 1;i <= m;i++){
        int a = read(),b = read(),c = read();
        v.push_back(node(a,b,c));
    }
    kruskal();
}

by _NTT_ @ 2021-12-30 16:15:38

@Joseph_H

int find(int u){
    return s[u] == u ? u : find(s[u]);
}

这样的find没有路径压缩，写成这样：

int find(int u){
    return s[u] == u ? u : s[u] = find(s[u]);
}

by _NTT_ @ 2021-12-30 16:16:39

@Joseph_H 另外没有判断图是否联通

by Joseph_H @ 2021-12-30 16:27:29

#include<bits/stdc++.h>
using namespace std;
const int NUM = 5e3 + 1;
int s[NUM];
void look(){
    printf("what happen?\n");
}
struct node{
    int u,v,w;
    node(int _u,int _v,int _w){
        u = _u;
        v = _v;
        w = _w;
    }
};
vector <node> v;
int find(int u){
    return s[u] == u ? u : s[u] = find(s[u]);
}
inline int read(){
    int now = 0,nev = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') nev = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        now = (now << 1) + (now << 3) + (c & 15);
        c = getchar();
    }
    return now * nev;
}
int n,m;
bool cmp(node a,node b){
    return a.w < b.w;
}
void kruskal(){
    int ans = 0;
    for(int i = 1;i <= n;i++){
        s[i] = i;
    }
    stable_sort(v.begin(),v.end(),cmp);
    for(int i = 0;i < m;i++){
        int b = find(v[i].u);
        int c = find(v[i].v);
        if(b == c) continue;
        s[c] = b;
        ans += v[i].w;
    }
    int flag = s[1];
    for(int i = 1;i <= n;i++){
        if(flag != s[i]){
            printf("orz");
            return;
        }
//      printf("%d ",s[i]);
    }
    printf("\n%d",ans);
}
int main(){
    n = read();
    m = read();
    for(int i = 1;i <= m;i++){
        int a = read(),b = read(),c = read();
        v.push_back(node(a,b,c));
    }
    kruskal();
}

改成这样就变成只A一个了

by Joseph_H @ 2021-12-30 16:27:49

@违规用户名TWnOO6x*

by Joseph_H @ 2021-12-30 16:28:59

如果联通的话，最后所有的s[i]都会一样的。

by Joseph_H @ 2021-12-30 16:32:51

把最后的printf("\n%d",ans); 改成printf("%d",ans);后变成wa2个\ 换行严判的luogu就是离谱

by Joseph_H @ 2021-12-30 16:34:54

好吧我是小丑 最后改为

int flag = find(1);
    for(int i = 1;i <= n;i++){
        if(flag != find(i)){
            printf("orz");
            return;
        }
    }

然后就AC了