題目大意： 在一個無向聯通圖中 求一棵最大邊與最小邊差值最小的生成樹 解題思路： 最大邊與最小邊差值最小的生成樹 換言之使得最小邊與最大邊的長度最接近 任取一條邊為生成樹最小的邊，唯一存在一條最大邊最接近最小的邊 對所有的邊從小到大排序 差值最小的最大邊一定在最小邊後面 並且是構成這個生成樹的最後一條邊！ 枚舉最小邊到第m－n＋2小邊組成的生成樹，找出差值最小的 易錯點： 最小邊和最大邊可能是同一條邊 代碼： [cpp] #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX 101 #define MAX_2 9000 #define INF 0x3f3f3f3f typedef struct snode{ int x; int y; int s; }span; int father[MAX]; int comp(const void *a,const void *b) { span *pa=(span *)a; span *pb=(span *)b; return pa->s-pb->s; } void Empty(int n) { int i; for(i=1;i<=n;i++) father[i]=i; } int Find(int x) { int s,j; s=x; while(x!=father[x]) x=father[x]; while(s!=x) { j=father[s]; father[s]=x; s=j; } return x; } void Union(int R1,int R2) { int r1,r2; r1=Find(R1); r2=Find(R2); if(r1!=r2) father[r1]=r2; } int main () { int n,m,i,j,min,start,end,num,a; while(scanf("%d%d",&n,&m)!=EOF) { span spantree[MAX_2]; if(m==0&&n==0) break; for(i=0;i<m;i++) { scanf("%d%d%d",&spantree[i].x,&spantree[i].y,&spantree[i].s); } qsort(spantree,m,sizeof(spantree[0]),comp); //把邊從小到大排序 for(i=0,end=0,start=0,min=INF;i<m-n+2;i++) //最多m-n+2個生成樹 { Empty(n); for(j=i,num=0;j<m;j++) { if(Find(spantree[j].x)!=Find(spantree[j].y)) { Union(spantree[j].x,spantree[j].y); num++; //某個生成樹的第num條邊 if(num==1) //第一條最小，num-1條最大 start=spantree[j].s; if(num==n-1) //易錯點**：是if不是else if,因為可能只有一條邊 end=spantree[j].s; } if(num==n-1) { a=end-start; if(a<min) { min=a; //找到最小的差值 } break; } } } if(min!=INF) printf("%d\n",min); else printf("-1\n"); } return 0; } #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX 101 #define MAX_2 9000 #define INF 0x3f3f3f3f typedef struct snode{ int x; int y; int s; }span; int father[MAX]; int comp(const void *a,const void *b) { span *pa=(span *)a; span *pb=(span *)b; return pa->s-pb->s; } void Empty(int n) { int i; for(i=1;i<=n;i++) father[i]=i; } int Find(int x) { int s,j; s=x; while(x!=father[x]) x=father[x]; while(s!=x) { j=father[s]; father[s]=x; s=j; } return x; } void Union(int R1,int R2) { int r1,r2; r1=Find(R1); r2=Find(R2); if(r1!=r2) father[r1]=r2; } int main () { int n,m,i,j,min,start,end,num,a; while(scanf("%d%d",&n,&m)!=EOF) { span spantree[MAX_2]; if(m==0&&n==0) break; for(i=0;i<m;i++) { scanf("%d%d%d",&spantree[i].x,&spantree[i].y,&spantree[i].s); } qsort(spantree,m,sizeof(spantree[0]),comp); //把邊從小到大排序 for(i=0,end=0,start=0,min=INF;i<m-n+2;i++) //最多m-n+2個生成樹 { Empty(n); for(j=i,num=0;j<m;j++) { if(Find(spantree[j].x)!=Find(spantree[j].y)) { Union(spantree[j].x,spantree[j].y); num++; //某個生成樹的第num條邊 if(num==1) //第一條最小，num-1條最大 start=spantree[j].s; if(num==n-1) //易錯點**：是if不是else if,因為可能只有一條邊 end=spantree[j].s; } if(num==n-1) { a=end-start; if(a<min) { min=a; //找到最小的差值 } break; } } } if(min!=INF) printf("%d\n",min); else printf("-1\n"); } return 0; }
