题目

有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组）【并查集，贪心】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。