題目

有n個村，m條路，給n-1條路刷油漆連接n個村，讓最長邊與最短邊的長度差最小。

---

輸入輸出（建議跳過）

Input

第一行給出一個數字TOT，代表有多少組數據,Tot<=6
對于每組數據，首先給出N，M
下面M行，每行三個數a,b,c代表a村與b的村道路距離為c.

Output

輸出最小差值,如果無解輸出”-1”.

Sample Input

1
4 5
1 2 3
1 3 5
1 4 6
2 4 6
3 4 7

Sample Output

1

---

解題思路

這道題數據比較小，首先記錄下所有邊，然后排序。枚舉最大邊，然后用并查集確定“村村通”的關系，然后取最小值。

---

代碼

#include<cstdio> #include<algorithm> #include<iostream> using namespace std; struct line{int x,y,w; }a[4951];//記錄邊 int father[101],n,mins,t,m; bool cmp(line dx,line dy) {return dx.w>dy.w; }//快排用 int find(int x) {if (x!=father[x]) return father[x]=find(father[x]);return x; }//并查集 void d(int x,int y) {father[find(x)]=find(y); }//連接 int main() {scanf("%d",&t);for (int ti=1;ti<=t;ti++){scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);}sort(a+1,a+1+m,cmp);//快排mins=214748364;for (int i=1;i<=m;i++)//枚舉最小邊{int j=i+1,k=1;//j表示枚舉到的邊，k表示選擇了的邊for (int q=1;q<=n;q++) father[q]=q;d(a[i].x,a[i].y);while (j<=m){if (find(a[j].x)!=find(a[j].y))//如果沒連接{d(a[j].x,a[j].y);//連接k++;//記錄}j+=1;//下一條if (k==n-1) break;//邊數足夠}if (j-1<=m && k==n-1)mins=min(mins,a[i].w-a[j-1].w);//取最小}if (n==2 && m==1 && a[1].x!=a[1].y) printf("0");//特殊情況判斷else if (mins==214748364) printf("-1\n");//無法連接else printf("%d\n",mins);//輸出} }

總結

以上是生活随笔為你收集整理的jzoj1751-Span（每日C组）【并查集，贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。