首页 > 代码库 > 【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