比赛 |
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;
}