首页 > 代码库 > 1589 Find The Most Comfortable Road
1589 Find The Most Comfortable Road
【原题】
http://acm.hdu.edu.cn/showproblem.php?pid=1598
【类型】
最小生成树+枚举
【题意】
给定一张无向有权图和一些询问，每一个询问都是一对起/终点，对于每一个询问，要求找到一条路能从起点到达终点，并且得到该条路上所有边权值中最大边与最小边的差，使得这个差值达到最小。最终的输出结果是这个差值。
【分析】
考虑Kruskal的贪心过程：将边从小到大排序，不断添边的过程中用并查集判断端点的归属情况。
假设在MST的寻找过程中，一对询问的其中一个点已经加入集合，当找到另外一个点加入集合的时刻寻找就可以结束，此时能够保证最后这条加入的边是已有的边中最大的，因为更大的边还在后面。
所以可以不断枚举最小边，以指定的最小边为基础进行Kruskal最小生成树操作，这里可能有两种情况：
1、最小边恰好在起/终点的路径上，则找到的最后一条边与最小边的差值即为这次查找的结果；
2、最小边不在起/终点的路径上，没有关系，因为后序枚举中仍然能够找出来。
因为使用了贪心性质，这里不能保证这个算法是最优解，但是可以保证结果的正确性。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 5 using namespace std; 6 7 typedef struct { 8 int a,b,c; 9 } node;10 node a[1001];11 12 bool op(node a,node b)13 {14 return a.c<b.c;15 }16 17 int father[201];18 19 void clean_father(int n)20 {21 for (int i=1;i<=n;i++) father[i]=i;22 }23 24 int getfather(int x)25 {26 if (father[x]!=x) father[x]=getfather(father[x]);27 return father[x];28 }29 30 void link(int x,int y)31 {32 father[getfather(x)]=getfather(y);33 }34 35 int main()36 {37 int n,m;38 while (scanf("%d%d",&n,&m)!=EOF)39 {40 for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);41 sort(&a[1],&a[m+1],op);42 43 int q;44 scanf("%d",&q);45 for (int i=1;i<=q;i++)46 {47 int t1,t2;48 scanf("%d%d",&t1,&t2);49 50 int minn,maxn,ans=2147483647;51 for (int j=1;j<=m;j++)52 {53 minn=2147483647;54 maxn=0;55 clean_father(n);56 for (int k=j;k<=m;k++)57 if (getfather(a[k].a)!=getfather(a[k].b))58 {59 link(a[k].a,a[k].b);60 if (minn>a[k].c) minn=a[k].c;61 if (maxn<a[k].c) maxn=a[k].c;62 if (maxn-minn>ans) break;63 if (getfather(t1)==getfather(t2))64 {65 if (ans>maxn-minn)66 {67 ans=maxn-minn;68 break;69 }70 }71 }72 }73 74 if (ans!=2147483647) printf("%d\n",ans);75 else printf("-1\n");76 }77 }78 79 return 0;80 }
1589 Find The Most Comfortable Road
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。