Continuar abriendo la ingeniería [Zhejiang University re-test on the next question] [Cover + Kruskal algorithm]

Descripción del tema

El objetivo de «ingeniería suave» del gobierno provincial es permitir el tráfico rodado en dos pueblos de la provincia (pero no tienen una carretera directa, siempre y cuando se pueda llegar a través de la carretera). Ahora, el costo de construir una carretera entre dos ciudades y pueblos arbitrarios está en la mesa, y si la carretera ha sido reparada. Ahora escribes un programa, calculas el costo mínimo de las necesidades universales en la provincia.

Descripción de la entrada:

Test input contains several test cases. The first line of each test case gives the number N (1 <n <100); the subsequent N (N-1) / 2 line corresponds to the cost and construction of the road between the village, and 4 positive integers per line, The number of two villages (from 1 number to N), the cost of the two villages, the cost, and the construction status: 1 indicated that it is built, 0 means not built.

 When N is 0, the input is ended.

Descripción de la salida:

The output of each test case occupies a row, and outputs the minimum cost required for universal needs in the province.

Ejemplo 1

Entrar

Copia

3
1 2 1 0
1 3 2 0
2 3 4 0
3
1 2 1 0
1 3 2 0
2 3 4 1
3
1 2 1 0
1 3 2 1
2 3 4 1
0

Salida

Copia

3
1
0

La idea que empecé es que como hay una manera de haber sido reparado, primero añadiré estos modos a la colección, es decir, directamente los pondré en unión, luego añadiré la longitud, y luego ordenaré, según el algoritmo Kruskal Come. Pero esta idea puede tener algún problema, sólo un caso general

El código del AC es: una vez que se ingresa la trayectoria, el valor de longitud es 0, después todas las trayectorias son consistentes

#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN=101;
int father[MAXN];
int height[MAXN];

struct edge {
	int from;
	int to;
	int len;
	int build;
	bool operator < (edge a)const {
// if (build &&! a.build) {// has been built in front
//			return true;
//		}
//		else if( build && a.build){
//			return false;
//		}
//
 // Else {// If it is not built or has been built, the length is small before
		return len<a.len;
//		}
	}
} edges[MAXN*MAXN];

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

int Find(int i) {
	if(i!=father[i]) {
		father[i]=Find(father[i]);
	}
	return father[i];
}

void Union(int i,int j) {
	i=Find(i);
	j=Find(j);
	if(i!=j) {
		if(height[i]>height[j]) {
			father[j]=i;
		} else if(height[j]>height[i]) {
			father[i]=j;
		} else {
			father[j]=i;
			height[i++];
		}
	}
	return ;
}

int Krual(int n,int edgenumber) {
	Init(n);
	int sum=0;
	sort(edges,edges+edgenumber);
	for(int i=0; i<edgenumber; i++) {
//		if(edges[i].build){
//			Union(edges[i].from,edges[i].to);
//		}
//		else{
//			if(Find(edges[i].from)!=Find(edges[i].to)){
//				Union(edges[i].from,edges[i].to);
//				sum+=edges[i].len;
//			}
//		}
		if(Find(edges[i].from)!=Find(edges[i].to)) {
			Union(edges[i].from,edges[i].to);
			sum+=edges[i].len;
		}
	}
	return sum;
}
int main() {
	int n;
	while(scanf("%d",&n)!=EOF) {
		if(n==0) {
			break;
		}
		int m=n*(n-1)/2;
		for(int i=0; i<m; i++) {
			scanf("%d%d%d%d",&edges[i].from,&edges[i].to,&edges[i].len,&edges[i].build);
			if(edges[i].build==1){
				edges[i].len=0;
			} 
		}
		printf("%dn",Krual(n,m));
	}
	return 0;
}