首页 > 代码库 > 【Kruskal】Slim Span
【Kruskal】Slim Span
[Uva1395]Slim Span
题目略……
试题分析:codevs1001舒适的路线上加一个判一下连通性就好,顺便把除改成减
代码:
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;inline int read(){ int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘; return x*f; }int N,M;struct data{ int x,y,v; }e[5001];bool cmp(data a,data b){ return a.v<b.v; }int fa[5001];void init(){ for(int i=1;i<=N;i++) fa[i]=i; return ; }int find(int x){ if(x!=fa[x]) return fa[x]=find(fa[x]); return x;}int ans1,ans2;int main(){ while(1){ N=read(),M=read(); if(!(N+M)) break; if(M==0){puts("-1");continue;} for(int i=1;i<=M;i++){ e[i].x=read(),e[i].y=read(); e[i].v=read(); } ans1=ans2=-1; bool alflag=false; sort(e+1,e+M+1,cmp); for(int i=1;i<=M;i++){ init(); for(int j=i;j<=M;j++){ int u=find(e[j].x),v=find(e[j].y);fa[v]=u; if(ans1!=-1&&e[j].v-e[i].v>=ans2-ans1) break; bool flag=false; for(int k=1;k<=N;k++) if(find(k)!=find(1)) {flag=true;break;} if(!flag){ans1=e[i].v;ans2=e[j].v;break;} } if(ans1==-1){puts("-1");alflag=true;break;} } if(!alflag)printf("%d\n",ans2-ans1); }}
【Kruskal】Slim Span
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。