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 = <<;
struct node
{
    int u,d;
    bool operator < (const node &b)const
    {
        return d>b.d;
    }
};
struct edge
{
    int v,w,next;
} e[*];
struct E
{
    int u,v,w;
};
vector<E> v;
int head[],vis[];
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,,sizeof(vis));
    q.push(s);
    vis[s]=;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(u==t)return true;
        for(int i=head[u]; i!=-; i=e[i].next)
        {
            int v=e[i].v;
            if(!vis[v])
            {
                vis[v]=;
                q.push(v);
            }
        }
    }
    return false;
}
void init()
{
    memset(head,-,sizeof(head));
    tot=;
}
bool check(int s,int t,int mid)
{
    for(int i=; 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,);
            addedge(v[j].v,v[j].u,);
        }
        if(bfs(s,t))
        {
            return ;
        }
    }
    return ;
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        v.clear();
        init();
        for(int i=; 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()-].w-v[].w;
        int LL=INF;
        for(int i=; i<v.size(); i++)
            LL=min(LL,v[i].w-v[i-].w);

        int q;
        scanf("%d",&q);
        while(q--)
        {
            int s,t;
            scanf("%d%d",&s,&t);
            int l=LL,r=RL+;
            while(l<r)
            {
                int mid=(l+r)>>;
                if(check(s,t,mid))
                    r=mid;
                else
                    l=mid+;
            }
            if(l==RL+)
                printf("-1\n");
            else
            printf("%d\n",l);
        }

    }
}
           

思路二

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

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = ;
int f[maxn];
struct edge
{
    int from,to,w;
} e[maxn*maxn+];
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=;
        for(i=; 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=<<;
            for(i=; i<m; i++)
            {
                for(int k=; 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!=<<)
                printf("%d\n",ans);
            else
                printf("-1\n");
        }
    }
}