1 files changed, 94 insertions, 0 deletions
diff --git a/inf/lige/1/4.c b/inf/lige/1/4.c
new file mode 100644
index 0000000..dfdf2a1
--- /dev/null
+++ b/inf/lige/1/4.c
@@ -0,0 +1,94 @@
+#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);
+}