求助大佬!样例都不过,没有输出
查看原帖
求助大佬!样例都不过,没有输出
359430
江户川コナン楼主2021/10/6 14:00

我用的是Kruskal,写完以后输入样例,竟然没有输出?求助大佬! 代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e4;
int n,m,s,t,b=0;
int fa[maxn];
struct node{
    int u,v,w;
    bool operator<(const node &x)const{
        return w<x.w;
    }
}edge[maxn];
void addEdge(int u,int v,int w){
    edge[++s]=(node){u,v,w};
}
void init(){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}
int get(int x){
    return fa[x]=(fa[x]==x)?x:get(fa[x]);
}
void merch(int x,int y){
    x=get(x);
    y=get(y);
    if(x!=y){
        fa[y]=x;
    }
}
int main(){
    cin>>n>>m>>s>>t;
    init();
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addEdge(u,v,w);
    }
    sort(edge+1,edge+1+m);
    for(int i=1;i<=m;i++){
        if(get(edge[i].u)!=get(edge[i].v)){
            merch(edge[i].u,edge[i].v);
            /*for(int i=1;i<=n;i++){
                cout<<get(i)<<" ";
            }
            cout<<endl;*/
        }
        if(get(t)==get(s)){
            //cout<<1<<endl;
            cout<<edge[i].w<<endl;
            return 0;
        }
    }
    return 0;
}

望大佬们指点迷津

2021/10/6 14:00
加载中...