题面
洛谷
题解
代码
(100pts)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return data * w;
}
#define MAX_N 5005
struct Graph { int to, next; } e[MAX_N * 10]; int fir[MAX_N], e_cnt;
void clearGraph() { memset(fir, -1, sizeof(fir)); e_cnt = 0; }
void Add_Edge(int u, int v) { e[e_cnt] = (Graph){v, fir[u]}; fir[u] = e_cnt++; }
int A, B, C;
int tot, xx[MAX_N], yy[MAX_N], zz[MAX_N];
int vis[MAX_N], dep, match[MAX_N];
bool dfs(int x) {
for (int i = fir[x]; ~i; i = e[i].next) {
int v = e[i].to;
if (dep != vis[v]) {
vis[v] = dep;
if (!match[v] || dfs(match[v])) {
match[v] = x;
return true;
}
}
}
return false;
}
int main() {
int T = gi();
int a, b, c, pos;
while (T--) {
tot = 0;
a = gi(), b = gi(), c = gi(), pos = 1;
if (b < a && b < c) pos = 2; else if (c < a && c < b) pos = 3;
for (int i = 1; i <= a; i++)
for (int j = 1; j <= b; j++)
for (int k = 1; k <= c; k++) {
int x = gi();
if (!x) continue;
else if (pos==1) ++tot, zz[tot]=i, xx[tot] = j, yy[tot] = k;
else if (pos==2) ++tot, zz[tot]=j, xx[tot] = i, yy[tot] = k;
else if (pos==3) ++tot, zz[tot]=k, xx[tot] = j, yy[tot] = i;
}
A = a, B = b, C = c;
if (pos == 2) swap(A, B);
if (pos == 3) swap(A, C);
int ans = 1e9;
for (int i = 0, sum; i < (1 << A); i++) {
for (int j = 1; j <= B; j++) match[j] = 0, fir[j] = -1;
e_cnt = 0;
sum = A;
for (int j = i; j; j -= (j & -j)) --sum;
for (int j = 1; j <= tot; j++)
if ((1 << (zz[j] - 1)) & i) Add_Edge(xx[j], yy[j]);
for (int j = 1; j <= B; j++) {
++dep;
if (dfs(j)) ++sum;
if (sum >= ans) break;
}
ans = min(ans, sum);
}
printf("%d
", ans);
}
return 0;
}