题面

洛谷

题解

代码

\(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\n", ans);

	}

	return 0;

}