首页 > 代码库 > HDU 1598 find the most comfortable road(并查集+枚举)
HDU 1598 find the most comfortable road(并查集+枚举)
先把每条边的权值从大到小排序,在一个个枚举,利用并查集判断是否在一个集合中。。。
<span style="font-size:24px;">#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<stdlib.h> #include<cmath> using namespace std; const int maxn=205; const int maxm=1005; const int inf=(0x7f7f7f7f); #define min(a,b) ((a)<(b)?(a):(b)) int fa[maxn]; int n,m; struct node { int x,y,z; }p[maxm]; bool cmp(node g,node h) { return g.z<h.z; } int find(int x) { while (fa[x] != x) x = fa[x]; return x; } int main() { int s,t; while(~scanf("%d%d",&n,&m)) { int i,j; for(i=0;i<m;i++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z); sort(p,p+m,cmp); int q; scanf("%d",&q); while(q--) { scanf("%d%d",&s,&t); int min1=inf; for(j=0;j<m;j++){ for(i=1;i<=n;i++) fa[i]=i; for(i=j;i<m;i++) { int fy=find(p[i].y); int fx=find(p[i].x); if(fy!=fx) fa[fy]=fx; if(find(s)==find(t)) { min1=min(min1,p[i].z-p[j].z); break; } } } if(min1==inf) puts("-1"); else printf("%d\n",min1); } } return 0; }</span>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。