[HDU1598]find the most comfortable road

思路：

考虑一个暴力：枚举最大的边权和最小的边权，然后将边权在这之间的边全拿出来构成一张无向图，剩下的就是判断是否存在一条从$S$到$T$的路径。
相当于判$S$和$T$是否连通，用并查集连一下即可。
时间复杂度：O(m³α(n))
考虑优化，枚举了最小边权之后，从小到大枚举最大边权，每次能新添加一条边。
因为并查集是支持动态加边的，所以复杂度就降到O(m²α(n))了。
一开始存边的vector忘记每次清零，一直Wrong Answer。

#include<cstdio>
#include<vector>
#include<algorithm>
const int inf=0x7fffffff;
struct Edge {
    int from,to,w;
    bool operator < (const Edge &x) const {
        return w<x.w;
    }
};
std::vector<Edge> e;
inline void add_edge(const int u,const int v,const int w) {
    e.push_back((Edge){u,v,w});
}
const int N=201;
class DisjointSet {
    private:
        int anc[N];
        int Find(const int x) {
            return x==anc[x]?x:anc[x]=Find(anc[x]);
        }
    public:
        void reset(const int n) {
            for(int i=1;i<=n;i++) anc[i]=i;
        }
        bool isConnected(const int x,const int y) {
            return Find(x)==Find(y);
        }
        void Union(const int x,const int y) {
            anc[Find(x)]=Find(y);
        }
};
DisjointSet s;
int main() {
    int n,m;
    while(~scanf("%d%d",&n,&m)) {
        e.clear();
        while(m--) {
            int s,t,w;
            scanf("%d%d%d",&s,&t,&w);
            add_edge(s,t,w);
        }
        std::sort(e.begin(),e.end());
        int q;
        scanf("%d",&q);
        while(q--) {
            int S,T;
            scanf("%d%d",&S,&T);
            int ans=inf;
            for(unsigned i=0;i<e.size();i++) {
                s.reset(n);
                for(unsigned j=i;j<e.size();j++) {
                    int &u=e[j].from,&v=e[j].to;
                    if(!s.isConnected(u,v)) {
                        s.Union(u,v);
                        if(s.isConnected(S,T)) {
                            ans=std::min(ans,e[j].w-e[i].w);
                            break;
                        }
                    }
                }
            }
            printf("%d
",ans!=inf?ans:-1);
        }
    }
    return 0;
}