Uva(1265)(Tour Belt)

链接：https://vjudge.net/problem/UVA-1265
思路：感觉最近做题都好没感觉啊，调试半天= =，这个题竟然直接n方暴力枚举边确实没想到，说一下思路，从大到小依次枚举两条边，若两边的都属于一个连通分量的内部，则更新这个内部的最小值，如果第二条边的某一个点与另一个点以及第一条边的祖先相等，说明第二条边之前已经枚举过，但与第一条边不属于一个连通分量，则此时更新一下最大值，然后比较一下最大值和最小值，若最小值保证大于最大值，则此时连通分量满足子图。
代码：

#include<bits/stdc++.h>
using namespace std;

int n,m,t;
const int maxn = 5010;

struct edge{
    int from,to,dist;
    edge(){}
    edge(int f,int t,int d){
        from = f;
        to = t;
        dist = d;
    }
    bool operator<(const edge &r){
        return dist>r.dist;
    }
};

struct Kruskal{
    vector<edge> edges;
    int n,m;
    int par[maxn];
    int ans;
    int done;
    int d[maxn];
    vector<int> G[maxn];
    int num[maxn];
    
    void init(int n){
        this->n = n;
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }

    void addedge(int from,int to,int dist){
        edges.push_back(edge(from,to,dist));
        m = edges.size();
        G[from].push_back(m-1);
    }

    int getroot(int a){
        if(a==par[a])return a;
        par[a] = getroot(par[a]);
        return par[a];
    }

    void merge(int a,int b){
        int p1 = getroot(a);
        int p2 = getroot(b);
        if(p1==p2)return;
        par[p2] = p1;
        num[p1]+=num[p2];
        num[p2] = 0;
    }

    void kruskal(){
        for(int i=0;i<=n;i++){
            par[i] = i;
            num[i] = 1;
        }
        sort(edges.begin(),edges.end());
        ans = 0;
        for(int i=0;i<edges.size();i++){
            int xx = getroot(edges[i].from);
            int yy = getroot(edges[i].to);
            if(xx!=yy){
                int minv = 1e9;
                int maxv = -1e9;
            merge(edges[i].from,edges[i].to);
            for(int j=0;j<edges.size();j++){
                int px = getroot(edges[j].from);
                int py = getroot(edges[j].to);
            if(px==py&&px==xx)minv = min(minv,edges[j].dist);
            else if(px==xx||py==xx)maxv = max(maxv,edges[j].dist);
            }
            if(minv>maxv)ans+=num[xx];
            }
    }
    }
}solver;

int main(){
   // freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        solver.init(n);
        for(int i=0;i<m;i++){
            int a,b,c;
            a--;
            b--;
            scanf("%d%d%d",&a,&b,&c);
            solver.addedge(a,b,c);
            solver.addedge(b,a,c);
        }
        solver.kruskal();
    printf("%d\n",solver.ans);
    }  
      return 0;
}