首页 > 代码库 > 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 100000000 struct 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"); else printf("%d\n",minn); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。