学步园

HDU_1598

一开始用Floyd写，结果WA掉了，怀疑是两存在点之间有多条路的情况。后来想到二分差值、枚举下界、判连通，但由于我是从权值着眼，依次递增去枚举下界的，结果由于数据范围太大果断超时了。后来看了网上的报告，他直接把所有的边先进行排序，然后以边为单位进行枚举下界，我于是恍然大悟，因为边的数量很少，只有1000条，所以以边为单位枚举下界，确实是个不错的选择。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXD 210
#define MAXM 1010
int N, M, u[MAXM], v[MAXM], w[MAXM], r[MAXM];
int p[MAXD], S, T;
int cmp(const void *_p, const void *_q)
{
int *p = (int *)_p;
int *q = (int *)_q;
return w[*p] - w[*q];
}
int find(int x)
{
return p[x] == x ? x : (p[x] = find(p[x]));
}
void init()
{
int e;
for(e = 0; e < M; e ++)
        scanf("%d%d%d", &u[e], &v[e], &w[e]);
}
int judge(int mid)
{
int i, j, tx, ty, limit;
for(i = 0; i < M; i ++)
    {
        limit = w[r[i]] + mid;
for(j = 1; j <= N; j ++)
            p[j] = j;
for(j = i ; j < M && w[r[j]] <= limit; j ++)
        {
            tx = find(u[r[j]]);
            ty = find(v[r[j]]);
if(tx != ty)
                p[tx] = ty;
        }
if(find(S) == find(T))
return 1;
if(j == M)
break;
    }
return 0;
}
void printresult()
{
int i, j, k, max, min, mid, ok, Q;
for(i = 0; i < M; i ++)
        r[i] = i;
    qsort(r, M, sizeof(r[0]), cmp);
    scanf("%d", &Q);
for(i = 0; i < Q; i ++)
    {
        scanf("%d%d", &S, &T);
        max = w[r[M - 1]] - w[r[0]] + 1;
        min = 0;
        ok = 0;
for(;;)
        {
            mid = (min + max) / 2;
            k = judge(mid);
if(k)
            {
                ok = 1;
                max = mid;
            }
if(mid == min)
break;
if(!k)
                min = mid;
        }
if(ok)
            printf("%d\n", max);
else
            printf("-1\n");
    }
}
int main()
{
while(scanf("%d%d", &N, &M) == 2)
    {
        init();
        printresult();
    }
return 0;
}