比赛 EYOI与SBOI开学欢乐赛7th 评测结果 AAAAATTTAAT
题目名称 中心台站建设 最终得分 63
用户昵称 lihaoze 运行时间 4.000 s
代码语言 C++ 内存使用 2.09 MiB
提交时间 2022-09-23 20:04:38
显示代码纯文本
#include <bits/stdc++.h>

const int N = 110;
std::vector<std::bitset<N>> a(N);
std::vector<std::vector<int>> res;
std::vector<int> chosen;
std::bitset<N> ans;
int n, min = 1e9;

void dfs(std::bitset<N> now, int cur) {
	if (chosen.size() > min) return;
	if (cur == n + 1) {
		if (now == ans) {
			if (chosen.size() < min) 
				res.clear(), min = chosen.size();
			res.emplace_back(chosen);
		}
		return;
	}
	chosen.emplace_back(cur);
	dfs(now | a[cur], cur + 1);
	chosen.pop_back();
	dfs(now, cur + 1);
}

int main() {
	freopen("zpj.in", "r", stdin);
	freopen("zpj.out", "w", stdout);
	std::cin >> n;
	for (int i = 1; i <= n; ++ i) ans[i] = true;
	for (int i = 1, x; i <= n; ++ i) {
		for (int j = 1; j <= n; ++ j)
			std::cin >> x, a[i][j] = x;
		a[i][i] = true;
	}
	dfs(std::bitset<N>(), 1);
	std::cout << min << '\n';
	std::cout << res.size() << '\n';
	for (auto i : res) {
		for (auto j : i)
			std::cout << j << ' ';
		std::cout << '\n';
	}
	return 0;
}