3316 - 最小差值生成树
CodeWaySky很早就学了最小生成树，所以CodeWaySky现在对简单的求最小生成树不感兴趣了。现在CodeWaySky想知道，对于一个给定的图，它的所有生成树中，最大边和最小边的边权差最小是多少。
因为CodeWaySky这个技术人员实在太忙了，到处帮大家解决问题，无法脱身，所以这个问题就交给你来解决了。
题目输入
第一行，两个用空格隔开的整数 N 和 M，分别表示顶点数和边数。
下面 M 行，每行 3 个数 u，v，w，表示 u 和 v 之间有一条权值为 w 的无向边。
题目输出
一行，一个非负整数，表示最大边和最小边的最小边权差。
若图本身不连通，则输出-1
输入/输出样例
题目输入
4 5 1 2 3 1 3 5 1 4 6 2 4 6 3 4 7
题目输出
1
提示
【数据范围】
20% M<=200
100% 2<=N<=100, 0<=M<=5000
C++解答
#include <cstdio> #include <cstring> #include <iostream> #include <cstdlib> #include <cmath> #include <ctime> #include <queue> #include <stack> #include <fstream> #include <algorithm> #include <map> using namespace std; int N,M; int my_max=0; int my_min=0x7fffffff; struct NODE{ int x,y; int va; }a[5005]; int ff[105],r1,r2; int f[105]; bool exist[10005]; int find(int x){ // cout<<x<<endl; if(x!=f[x])f[x]=find(f[x]); return f[x]; } int ffind(int x){ if(ff[x]!=x)ff[x]=ffind(ff[x]); return ff[x]; } bool tepan(){ for(int i=1;i<=N;i++)ff[i]=i; for(int i=1;i<=M;i++){ r1=ffind(a[i].x); r2=ffind(a[i].y); if(r1!=r2){ if(r1>r2)swap(r1,r2); ff[r2]=r1; } } for(int i=1;i<=N;i++)if(ffind(i)==i&&i!=1)return true; return false; } int comp(const NODE &X,const NODE &Y){ return X.va<Y.va; } bool bing(int s1,int s2){ for(int i=s1;i<=s2;i++){ r1=find(a[i].x); r2=find(a[i].y); if(r1!=r2){ if(r1>r2)swap(r1,r2); f[r2]=r1; } } for(int i=1;i<=N;i++)if(find(i)==i&&i!=1)return false; return true; } bool judge(int x){ int stj,t,j; memset(exist,0,sizeof(exist)); for(int i=1;i<=M;i++){ while(exist[a[i].va]==true)i++; t=a[i].va;//bool标记用过次边权 exist[a[i].va]=true; j=i+1; while(a[j].va-a[i].va<=x){ j++; if(j>M)break; } for(int v=1;v<=N;v++)f[v]=v; if(bing(i,j-1))return false;//如果此区间内的边并起来满足的话，差值大了 } return true;//怎么并都不行 } void work(){ int l=0; int r=my_max-my_min; int mid=(l+r)/2; while(l<=r){ mid=(l+r)/2; if(judge(mid))l=mid+1; else r=mid-1; } cout<<l<<endl; } int main(){ // freopen("1.in","r",stdin); //freopen("span.in","r",stdin); //freopen("span.out","w",stdout); scanf("%d%d",&N,&M); for(int i=1;i<=M;i++){ scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].va); my_max=my_max>a[i].va? my_max:a[i].va; my_min=my_min<a[i].va? my_min:a[i].va; } if(tepan()){ cout<<-1<<endl; return 0; } sort(a+1,a+M+1,comp); work(); fclose(stdin); fclose(stdout); return 0; }
提示
【数据范围】
20% M<=200
100% 2<=N<=100, 0<=M<=5000