Cod sursa(job #1684618)

Utilizator FernandoSandoiu Fernando Fernando Data 11 aprilie 2016 10:45:10
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.52 kb
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

struct muchie{
	long varf1, varf2;
	long cost;
}muchii[1000], newArb[1000];

FILE *fout = fopen("apm.out", "w");

long compconex[1000],newNrMuchii;

void randomquick(struct muchie muchii[100], int first, int last){
	struct muchie tmp;
	int i = first, j = last, pivot;
	pivot = muchii[first + rand() % (first + last + 1)].cost;
	while (i <= j)
	{
		while (muchii[i].cost < pivot)
			i++;
		while (muchii[j].cost > pivot)
			j--;
		if (i <= j)
		{
			tmp = muchii[i];
			muchii[i++] = muchii[j];
			muchii[j--] = tmp;
		}
	}
	if (first < j)
		randomquick(muchii, first, j);
	if (last>i)
		randomquick(muchii, i, last);

}

int find_set(int i)
{
	while (compconex[i])
	{
		i = compconex[i];
	}

	return i;
}

void kruskal(struct muchie muchii[1000], long compconex[1000], long nrMuchii,long nrNoduri)
{
	int i;
	for (i = 1; i <= nrNoduri; i++)
	{
		compconex[i] = 0;
	}
	int set1, set2,k;
	i = 0;
	while (i <= nrMuchii && newNrMuchii < nrNoduri - 1)
	{
		set1 = find_set(muchii[i].varf1);
		set2 = find_set(muchii[i].varf2);
		if (set1 != set2)
		{
			newArb[newNrMuchii] = muchii[i];
			newNrMuchii++;
			compconex[set2] = set1;
		}
		i++;
	}
	int cost = 0;
	//printf("Kruskal:\n");
	for (i = 0; i < newNrMuchii; i++)
	{
		//printf("%d %d %d\n", newArb[i].varf1, newArb[i].varf2, newArb[i].cost);
		cost += newArb[i].cost;
	}
	fprintf(fout, "%d\n", cost);
	for (i = 0; i < newNrMuchii; i++)
	{
		fprintf(fout,"%d %d\n", newArb[i].varf2, newArb[i].varf1);
		//cost += newArb[i].cost;
	}
	//printf("Costul minim este: %d\n", cost);
}

int main()
{
	long nrMuchii=0;
	FILE *fp = fopen("apm.in", "r");
	long i,nrNoduri=0;
	int x, y;
	fscanf(fp, "%d%d", &x, &y);
	while ((fscanf(fp, "%d%d%d", &muchii[nrMuchii].varf1, &muchii[nrMuchii].varf2, &muchii[nrMuchii].cost))!=EOF)
	{
		nrMuchii++;
		if (muchii[nrMuchii-1].varf1 > nrNoduri)
			nrNoduri = muchii[nrMuchii-1].varf1;
		if (muchii[nrMuchii-1].varf2 > nrNoduri)
			nrNoduri = muchii[nrMuchii-1].varf2;
	}
	nrMuchii--;
	srand(time(0)*clock());
	randomquick(muchii, 0, nrMuchii);
	/*for (i = 0; i <= nrMuchii; i++)
	{
		fprintf(stdout, "%d %d %d\n", muchii[i].varf1, muchii[i].varf2, muchii[i].cost);
	}*/
	kruskal(muchii, compconex, nrMuchii, nrNoduri);
	fclose(fp);
	return 0;
}

/*1 2 7
1 4 5
2 3 8
2 4 9
2 5 7
3 5 5
4 5 15
4 6 6
5 6 8
5 7 9
6 7 11


1 2 4
1 8 8
2 8 11
2 3 8
3 9 2
3 6 4
3 4 7
4 6 14
4 5 9
5 6 10
6 7 2
7 8 1
7 9 6
8 9 7
*/