【HNOI2013】消毒

题面

题解

当只有二维时，就是一个二分图匹配的板子题

三维的时候就很好做了，暴力枚举一维的情况，因为\(\min(x,y,z) = \sqrt{5000} < 18\)，于是时间复杂度有保证

代码

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#define RG register

#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);

#define clear(x, y) memset(x, y, sizeof(x))

inline int read()

{

	int data = 0, w = 1; char ch = getchar();

	while(ch != '-' && (!isdigit(ch))) ch = getchar();

	if(ch == '-') w = -1, ch = getchar();

	while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();

	return data * w;

}

const int maxn(5010);

struct edge { int next, to; } e[maxn];

int head[maxn], e_num, a, b, c, Min, pos[4][maxn], vis[maxn], match[maxn], clean[maxn], ans, cnt, T;

inline void add_edge(int from, int to) { e[++e_num] = (edge) {head[from], to}; head[from] = e_num; }

bool dfs(int x)

{

	for(RG int i = head[x]; i; i = e[i].next)

	{

		int to = e[i].to; if(vis[to]) continue; vis[to] = true;

		if(!match[to] || dfs(match[to])) return match[to] = x, true;

	}

	return false;

}

inline void Doit(int x)

{

	using std::fill; e_num = 0;

	fill(head + 1, head + b + 1, 0);

	fill(match + 1, match + c + 1, 0);

	fill(clean + 1, clean + a + 1, 1);

	int res = 0;

	for(RG int i = 0; i < a; i++)

		if(x & (1 << i)) clean[i + 1] = 0, ++res;

	for(RG int i = 1; i <= cnt; i++)

		if(clean[pos[1][i]]) add_edge(pos[2][i], pos[3][i]);

	for(RG int i = 1; i <= b; i++)

	{

		fill(vis + 1, vis + c + 1, 0);

		if(dfs(i)) ++res;

	}

	ans = std::min(ans, res);

}

int main()

{

	T = read();

	while(T--)

	{

		cnt = 0; ans = 0x3f3f3f3f;

		a = read(); b = read(); c = read(); Min = std::min(std::min(a, b), c);

		for(RG int i = 1, x; i <= a; i++)

			for(RG int j = 1; j <= b; j++)

				for(RG int k = 1; k <= c; k++)

					if((x = read())) ++cnt, pos[1][cnt] = i, pos[2][cnt] = j, pos[3][cnt] = k;

		using std::swap;

		if(Min == b) swap(a, b), swap(pos[1], pos[2]);

		if(Min == c) swap(a, c), swap(pos[1], pos[3]);

		for(RG int i = 0; i < (1 << a); i++) Doit(i);

		printf("%d\n", ans);

	}

	return 0;

}

巴特西

【HNOI2013】消毒

题面

题解

代码

最新文章

热门文章