题解 | #继续畅通工程#

#include using namespace std; #include

const int MAXN=100; int father[MAXN]; struct Edge{ int from; int to; int length; int state;

bool operator<(const Edge&a)const{
    return this->length < a.length;
}

};

Edge e[MAXN*MAXN];

void Initial(int n){ for(int i=0;i<=n;i++){ father[i]=i; } }

int find_s(int x){ //并查集中的查找 if(x!=father[x]){ father[x]=find_s(father[x]); } return father[x]; }

void Union(int x,int y){ //并查集中的合并 x=find_s(x); y=find_s(y); if(x!=y){ father[x]=y; } }

int Kruskal(int n,int edgeNumber){ //定义克鲁斯卡尔算法 Initial(n); sort(e, e+edgeNumber); int sum=0; for(int i=0;i<edgeNumber;i++){ Edge current=e[i]; if(find_s(current.from)!=find_s(current.to)){ Union(current.from, current.to); sum+=current.length; } } return sum; }

int main(){ int n; while(cin>>n){ if(n==0){ break; } int edgeNumber=n*(n-1)/2; for(int i=0;i<edgeNumber;i++){ cin>>e[i].from>>e[i].to>>e[i].length>>e[i].state; if(e[i].state==1){ e[i].length=0; } } int answer=Kruskal(n, edgeNumber); cout<<answer<<endl; } return 0; }