path: root/inf/lige/1/4.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct cesta {
	int w;
	int x;
	int y;
};
int primerjaj_ceste (const void * a, const void * b) {
	const struct cesta * c = (const struct cesta *) a;
	const struct cesta * d = (const struct cesta *) b;
	return c->w - d->w;
}
void obisci (char * adj, int n, int x, char * obiskal) {
	obiskal[x] = 1;
	char * off = adj + x*n;
	for (int i = 0; i < n; i++)
		if (off[i] && !obiskal[i])
			obisci(adj, n, i, obiskal);
}
int povezan (char * adj, int n) {
	char * obiskal = calloc(n, sizeof *obiskal);
	obisci(adj, n, 0, obiskal);
	for (int i = 0; i < n; i++)
		if (!obiskal[i]) {
			free(obiskal);
			return 0;
		}
	free(obiskal);
	return 1;
}
int main (void) {
	char buf[128];
	fgets(buf, 128, stdin);
	char * c = buf;
	int n = strtol(c, &c, 10);
	c++;
	int m = strtol(c, &c, 10);
	int i = m;
	struct cesta * ceste = calloc(m, sizeof *ceste);
	int skupen_w = 0;
	char * adj = calloc(n*n, sizeof *adj);
	while (i--) {
		fgets(buf, 128, stdin);
		c = buf;
		ceste[i].x = strtol(c, &c, 10)-1;
		ceste[i].y = strtol(++c, &c, 10)-1;
		skupen_w += ceste[i].w = strtol(++c, &c, 10);
		adj[n*ceste[i].x+ceste[i].y]++;
		adj[n*ceste[i].y+ceste[i].x]++;
	}
	qsort(ceste, m, sizeof(struct cesta), primerjaj_ceste);
#ifdef xxx
	for (int i = 0; i < m; i++)
		printf("w: %d\tpovezava: %d\t%d\n", ceste[i].w, ceste[i].x, ceste[i].y);
#endif
	int od_w = 0;
	/*
	if (!povezan(adj, n)) {
		fprintf(stderr, "NI POVEZAN!\n");
		for (int i = 0; i < n*n; i++) {
			fprintf(stderr, "%d ", adj[i]);
			if (!((i+1)%n))
				fprintf(stderr, "\n");
		}
	}
	*/
	for (int i = m-1; i >= 0; i--) {
		adj[n*ceste[i].x+ceste[i].y] = 0;
		adj[n*ceste[i].y+ceste[i].x] = 0;
		if (!povezan(adj, n)) {
			adj[n*ceste[i].x+ceste[i].y]++;
			adj[n*ceste[i].y+ceste[i].x]++;
		} else {
			od_w += ceste[i].w;
		}
	}
	/*
	fprintf(stderr, "skupen_w: %d\n", skupen_w);
	for (int i = 0; i < m; i++) {
		if (adj[n*ceste[i].x + ceste[i].y] == 0) {
			fprintf(stderr, "x\n");
			izbran_w += ceste[i].w;
			adj[n*ceste[i].x + ceste[i].y]++;
			adj[n*ceste[i].y + ceste[i].x]++;
		}
		if (povezan(adj, n)) {
			fprintf(stderr, "POVEZAN!\n");
		} else if (i == m-1)
			fprintf(stderr, "NAPAKA!\n");
	}
	*/
	printf("%d\n", od_w);
}