HDU 1598 find the most comfortable road 二分+bfs or 并查集枚举

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1598

题意

中文题：找到一条s到t的路，其中边的差值最小，输出这个差值，如果不存在输出-1。

思路1.

枚举差值，先将边保存起来，获得最大最小边权差值（二分的上界下界）。枚举一个差值，将符合差值的边加入图中，跑bfs，看从s是否能够到达t，我这儿输出-1的处理是给上界是加了个1，如果最后答案出界了，说明不存在s到t的路线。也是失了智，把m写错n，一直在re(╥╯^╰╥)

#include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> using namespace std; const int INF = 1<<30; struct node { int u,d; bool operator < (const node &b)const { return d>b.d; } }; struct edge { int v,w,next; } e[2*1010]; struct E { int u,v,w; }; vector<E> v; int head[210],vis[210]; int tot; bool cmp(E a,E b) { return a.w<b.w; } void addedge(int u,int v,int w) { e[tot].v=v; e[tot].w=w; e[tot].next=head[u]; head[u]=tot++; } bool bfs(int s,int t) { queue<int> q; memset(vis,0,sizeof(vis)); q.push(s); vis[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); if(u==t)return true; for(int i=head[u]; i!=-1; i=e[i].next) { int v=e[i].v; if(!vis[v]) { vis[v]=1; q.push(v); } } } return false; } void init() { memset(head,-1,sizeof(head)); tot=0; } bool check(int s,int t,int mid) { for(int i=0; i<v.size(); i++) { int low=v[i].w; init(); for(int j=i; j<v.size(); j++) { if(v[j].w-low>mid)break; addedge(v[j].u,v[j].v,1); addedge(v[j].v,v[j].u,1); } if(bfs(s,t)) { return 1; } } return 0; } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { v.clear(); init(); for(int i=0; i<m; i++) { int u,V,w; scanf("%d%d%d",&u,&V,&w); v.push_back(E{u,V,w}); } sort(v.begin(),v.end(),cmp); int RL=v[v.size()-1].w-v[0].w; int LL=INF; for(int i=1; i<v.size(); i++) LL=min(LL,v[i].w-v[i-1].w); int q; scanf("%d",&q); while(q--) { int s,t; scanf("%d%d",&s,&t); int l=LL,r=RL+1; while(l<r) { int mid=(l+r)>>1; if(check(s,t,mid)) r=mid; else l=mid+1; } if(l==RL+1) printf("-1\n"); else printf("%d\n",l); } } }

思路二

和UVA1395类似的做法，uva这道题是求最小生成树中最大最小边权差值最小。这里只要s和t连通就可以判断了。

#include<cstdio> #include<algorithm> using namespace std; const int maxn = 110; int f[maxn]; struct edge { int from,to,w; } e[maxn*maxn+20]; bool cmp(edge a,edge b) { return a.w<b.w; } int Find(int x) { return f[x]==x?x:f[x]=Find(f[x]); } int main() { int n,m; //n=[2,100] // freopen("in.txt","r",stdin); while(~scanf("%d%d",&n,&m)&&(m+n)) { int i=0; for(i=0; i<m; i++) scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].w); sort(e,e+m,cmp); int q; scanf("%d",&q); while(q--) { int s,t; scanf("%d%d",&s,&t); int ans=1<<30; for(i=0; i<m; i++) { for(int k=1; k<=n; k++)f[k]=k; int j=i; for(; j<m; j++) { int u=e[j].from,v=e[j].to; int xx=Find(u); int yy=Find(v); if(xx!=yy) { f[xx]=yy; } if(Find(s)==Find(t)) { if(ans>(e[j].w-e[i].w)) { ans=(e[j].w-e[i].w); } break; } } } if(ans!=1<<30) printf("%d\n",ans); else printf("-1\n"); } } }