aoc

commit f5f17d7c64588d97394e6372dea4252146d846ab
parent 60858697b199d089ef78451d51063743f9b6f6d1
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Mon, 25 Dec 2023 12:14:15 +0100

Merry Christmas!

Diffstat:
A
2023/25/25a.c
 | 
95
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 95 insertions(+), 0 deletions(-)
diff --git a/2023/25/25a.c b/2023/25/25a.c
@@ -0,0 +1,95 @@
+#include <inttypes.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define N 1500
+#define M 15000
+#define MIN(x,y) ((x)<(y)?(x):(y))
+#define ischar(c) (c >= 'a' && c <= 'z')
+
+typedef struct {
+	int nout, out[N];
+	char s[4], outc[N][4];
+} node_t;
+
+bool visited[N];
+char *buf, line[N][N];
+int n, nother, c[N][N], f[N][N];
+node_t m[N];
+
+int findm(char *s) {
+	for (int k = 0; k < n; k++)
+		if (m[k].s[0] == s[0] && m[k].s[1] == s[1] && m[k].s[2] == s[2])
+			return k;
+	return n;
+}
+
+void resetfc(void) {
+	for (int i = 0; i < n; i++)
+		for (int j = 0; j < m[i].nout; j++)
+			c[i][m[i].out[j]] = 1;
+	for (int i = 0; i < n; i++)
+		memset(f[i], 0, N * sizeof(int));
+}
+
+bool dfs(int v, int t) {
+	if (v == t) return true;
+	if (visited[v]) return false;
+	visited[v] = true;
+	for (int i = 0; i < m[v].nout; i++) {
+		int u = m[v].out[i];
+		if (c[v][u] == 0) continue;
+		c[v][u]--;
+		c[u][v]++;
+		f[v][u]++;
+		if (dfs(u, t)) return true;
+		c[v][u]++;
+		c[u][v]--;
+		f[v][u]--;
+	}
+	return false;
+}
+
+bool residualpath(int s, int t) {
+	memset(visited, 0, N * sizeof(bool));
+	return dfs(s, t);
+}
+
+/* Ford-Fulkerson */
+bool flowatmost(int s, int t, int k) {
+	int flow;
+	resetfc();
+	for (flow = 0; flow <= k && residualpath(s, t); flow++) ;
+	return flow <= k;
+}
+
+int main() {
+	for (n = 0; (buf = fgets(line[n], N, stdin)) != NULL; n++) {
+		for (int i = 0; ischar(*buf); m[n].s[i++] = *(buf++)) ;
+		for (int i = 0; *buf != '\n'; i++) {
+			while (!ischar(*buf)) buf++;
+			for (int j = 0; ischar(*buf); m[n].outc[i][j++] = *(buf++)) ;
+		}
+	}
+
+	for (int i = 0; i < n; i++) {
+		for (int j = 0; m[i].outc[j][0]; j++) {
+			int k = findm(m[i].outc[j]);
+			m[i].out[m[i].nout++] = k;
+			m[k].out[m[k].nout++] = i;
+			if (k == n) {
+				for (int k = 0; m[i].outc[j][k]; k++)
+					m[n].s[k] = m[i].outc[j][k];
+				n++;
+			}
+		}
+	}
+
+	for (int t = 1; t < n; t++)
+		if (flowatmost(0, t, 3)) nother++;
+
+	printf("%d (%d %d)\n", nother * (n-nother), nother, n-nother);
+	return 0;
+}