HDu 6187 Destroy Walls(最大生成ツリー)

タイトル:
nとmは、2次元平面上にn個の点があることを示す、mは壁を塞いで、各点の2次元平面上の座標を与えて、第iは壁を塞いで(u,v)、壁に塞がれた場所は歩けない.各壁の取り外しには1つの代価があり、現在、少なくともどれだけの壁を取り外すかを聞いて、各点が他の点(図連通)に到達できるように、最小限の取り外しを前提に代価をできるだけ少なくし、最小限の取り外しと最小の代価を出力することができる.
データ範囲:n<=1 e 5、m<=2 e 5、壁に自環と重辺が存在しないことを保証する
解法:

        (          )

             ,
                ,

    ,           ,
                ,
              ,            .

          ,              ,
                 ,        .
            ,            ,         .

      :
            ,   kruskal         ,
         n-1,                   .

code:

#include
using namespace std;
const int maxm=1e6+5;
struct Node{
    int a,b,c;
}e[maxm];
int pre[maxm];
int n,m;
int ffind(int x){
    return pre[x]==x?x:pre[x]=ffind(pre[x]);
}
bool cmp(Node a,Node b){
    return a.c>b.c;
}
signed main(){
    ios::sync_with_stdio(0);
    while(cin>>n>>m){
        for(int i=1;i<=n;i++)pre[i]=i;
        for(int i=1;i<=n;i++){
            int x,y;cin>>x>>y;
        }
        int tot=0;
        for(int i=1;i<=m;i++){
            int a,b,c;cin>>a>>b>>c;
            e[i]={a,b,c};
            tot+=c;
        }
        sort(e+1,e+1+m,cmp);
        int cnt=0;
        int sum=0;
        for(int i=1;i<=m;i++){
            int x=ffind(e[i].a);
            int y=ffind(e[i].b);
            if(x!=y){
                pre[x]=y;
                sum+=e[i].c;
                cnt++;
                if(cnt==n-1)break;
            }
        }
        cout<<m-cnt<<' '<<tot-sum<<endl;
    }
    return 0;
}