PIPIOJ 1118: 继续畅通工程 最小生成树kruskal算法

题目：

http://39.106.164.46/problem.php?id=1118

Kruskal算法：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#include<set>
#define MAX 105
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;int n,fa[MAX];struct edge{
    int a,b,len;int tag;bool operator < (const edge &x) const{
    return len<x.len;}
}e[MAX*MAX];int findfather(int x){
    if(x==fa[x]) return fa[x];else return fa[x]=findfather(fa[x]);
}int main(){
    while(cin>>n){
    if(n==0) break;int a,b,len,c;for(int i=0;i<MAX;i++){
    fa[i]=i;}int m=n*(n-1)/2;for(int i=0;i<m;i++){
    cin>>e[i].a>>e[i].b>>e[i].len>>e[i].tag;if(e[i].tag==1){
    int aa=findfather(e[i].a),bb=findfather(e[i].b);fa[aa]=bb;}}sort(e,e+m);int ans=0;for(int i=0;i<m;i++){
    int aa=findfather(e[i].a),bb=findfather(e[i].b);if(aa!=bb){
    fa[aa]=bb;ans+=e[i].len;}}cout<<ans<<endl;}return 0;
}