hdu 1598 find the most comfortable road (并查集 + 枚举)

本文主要是介绍hdu 1598 find the most comfortable road (并查集 + 枚举)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

        链接：点击打开链接

思路：

        对边排序，再枚举每条边，如果出现通路（findset(x) == findset(y)）就结束。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 220
#define MAXM 1010
#define MAX 100000000struct node{int s,e,w;
}edge[MAXM];int root[MAXN];
int n,m,q;int cmp(node a,node b)
{return a.w < b.w;
}int findset(int x)
{return root[x] == x ? x : root[x] = findset(root[x]);
}void mergeset(int x,int y)
{root[findset(x)] = findset(y);
}void init()
{for(int i=1; i<=n; i++)root[i] = i;
}int main()
{//freopen("input.txt","r",stdin);int x,y;int minn;while(scanf("%d%d",&n,&m) != EOF){int i,j;for(i=0; i<m; i++){scanf("%d%d%d",&edge[i].s,&edge[i].e,&edge[i].w);}sort(edge,edge+m,cmp);scanf("%d",&q);while(q--){scanf("%d%d",&x,&y);minn = MAX;for(i=0; i<m; i++){init();for(j=i; j<m; j++){mergeset(edge[j].s,edge[j].e);if(findset(x) == findset(y))break;}if(j == m)break;if(minn > edge[j].w - edge[i].w)minn = edge[j].w - edge[i].w;}if(minn == MAX)printf("-1\n");elseprintf("%d\n",minn);}}return 0;
}

这篇关于hdu 1598 find the most comfortable road (并查集 + 枚举)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---