最小生成树求助
  • 板块P1396 营救
  • 楼主ZM____ML
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/3/23 21:19
  • 上次更新2023/10/23 20:44:53
查看原帖
最小生成树求助
694461
ZM____ML楼主2023/3/23 21:19

30pts

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e4+5;
int n,m,s,t,f[N];
struct node{
    int x,y,cost;
    friend bool operator<(node x,node y){
    	return x.cost>y.cost;
	} 
}b[N];

inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return x*f;
}

int find(int x){
    if(x==f[x])return x;
    return f[x]=find(f[x]);
}

int main(){
    n=read(),m=read(),s=read(),t=read();
    for(int i=1;i<=m;i++)f[i]=i;
    for(int i=1;i<=m;i++)b[i].x=read(),b[i].y=read(),b[i].cost=read();
    sort(b+1,b+m+1);
    for(int i=1;i<=m;i++){
        int x=find(b[i].x),y=find(b[i].y);
        if(x!=y)f[x]=y;
        if(find(s)==find(t)){
        	printf("%d",b[i].cost);
            return 0;
        }
    }
    return 0;
}
2023/3/23 21:19
加载中...