题解 | 继续畅通工程

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> fa(110);
void init(int n){
    //fa.clear();
    //fa.resize(n+1);   // 重新分配空间
	for(int i=0;i<=n;i++)fa[i]=i;
	return;
}
int find(int x){
	if(x!=fa[x])fa[x]=find(fa[x]);
	return fa[x];
}
void join(int x,int y){
	x=find(x);
	y=find(y);
	if(x!=y)fa[y]=fa[x];
}
struct Edg{
	int l,r,val,f;
};
bool com(const Edg &a,const Edg &b){
	return a.val<b.val;
}
int main(){
	int n;
	while(cin>>n){
		if(n==0)break;
	vector<Edg> edg;
     init(n);
	int a,b,c,d,t;
	t=n*(n-1)/2;
	while(t--){
		cin>>a>>b>>c>>d;
		if(d==0){
			Edg e={a,b,c,d};
			edg.push_back(e);
		}else join(a,b);
	}
	sort(edg.begin(),edg.end(),com);
	int res=0;
	int x,y;
	for(int i=0;i<edg.size();i++){
		x=find(edg[i].l);
		y=find(edg[i].r);
		if(x!=y){
			if(edg[i].f==0)res+=edg[i].val;
			join(x,y);
		}
	}
	cout<<res<<endl;

	} 

	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
}