hdu1598 find the most comfortable road 并查集

hdu1598 find the most comfortable road 并查集

<pre name="code" class="cpp">#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=200+10;  //point
const int maxm=1000+10; //edge
int p[maxn],r[maxn],n,m;
struct node
{
    int s,e;    //start end
    int w;      //speed
}edge[maxm];
void make()
{
    memset(p,-1,sizeof(p));
    memset(r,0,sizeof(r));
}
int findset(int x)
{
    int px=x,tmp;
    while (p[px]!=-1)   px=p[px];
    while (px!=x) {
        tmp=p[x];
        p[x]=px;
        x=tmp;
    }
    return px;
}
int unionset(int x,int y)
{
    x=findset(x),y=findset(y);
    if(x==y)    return -1;
    if(r[x]>r[y])
    {
        p[y]=x;return x;
    }
    else
    {
        p[x]=y;
        if(r[x]==r[y])  r[y]++;
        return y;
    }
}
bool cmp(node a,node b)
{
    return a.w<b.w;
}
int main()
{
    while (scanf("%d%d",&n,&m)!=EOF) {
        for (int i=0; i<m; i++) {
            scanf("%d%d%d",&edge[i].s,&edge[i].e,&edge[i].w);
        }
        sort(edge,edge+m,cmp);
        int k,x,y;
        scanf("%d",&k);
        while (k--) {
            int mint=0x3f3f3f3f,start,end;
            scanf("%d%d",&x,&y);
            for(start=0;start<m;start++)
            {
                make();
                for(end=start;end<m;end++)//最小速度为edge[i].w时，求最小速度差.
                {
                    unionset(edge[end].s, edge[end].e);
                    if(findset(x)==findset(y))  break;//x与y之间已经形成通路
                }
                if(end==m)    break;//不能成环，若start时不能成环，则start+1也不能成环
                mint=min(edge[end].w-edge[start].w,mint);//更新最小速度差的最小值mint.
            }
            printf("%d\n",mint==0x3f3f3f3f?-1:mint);
        }
    }
    return 0;
}</pre>

<pre name="code" class="cpp"></pre>