NC19045. Cliques
描述
输入描述
The first line of the input contains an integer t which is the number of test cases. For each test case, the first line consists of an integer n (1 ≤ n ≤ 100) which is the number of nodes in undirected graph G. Each of the following n lines consists of n integers corresponding to the adjacency matrix of G where 1 represents the existence of the edge and 0 otherwise.
输出描述
For each test case, output first the case number, see the sample output. There should be a space after the colon in each test case. Then, if the graph G can be modified into a new graph with no more than ten steps, output the minimum number of steps we need, or −1 if not.
示例1
输入:
2 7 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0
输出:
Case #1: 2 Case #2: 0
C++14(g++5.4) 解法, 执行用时: 1089ms, 内存消耗: 420K, 提交时间: 2020-06-09 19:08:21
#include<bits/stdc++.h>
using namespace std;
bool e[101][101];
int n, ans;
void rot(int a, int b) {
e[a][b] ^= 1, e[b][a] ^= 1;
}
void dfs(int step) {
if(step >= ans) {
return;
}
int a = 0, b, c;
for(int i = 1; i <= n && !a; i++) {
for(int j = i + 1; j <= n && !a; j++) {
if(e[i][j]) {
for(int k = 1; k <= n && !a; k++) {
if(k != i && k != j && (e[i][k] ^ e[j][k])) {
a = i, b = j, c = k;
}
}
}
}
}
if(!a) {
ans = step;
return;
}
rot(a, b);
dfs(step + 1);
rot(a, b);
rot(b, c);
dfs(step + 1);
rot(b, c);
rot(a, c);
dfs(step + 1);
rot(a, c);
}
int main() {
cin.sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
for(int cas = 1; cas <= T; cas++) {
cout << "Case #" << cas << ": ";
cin >> n;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
int x;
cin >> x;
e[i][j] = (x > 0);
}
}
ans = 11;
dfs(0);
if(ans == 11) {
cout << "-1\n";
} else {
cout << ans << '\n';
}
}
return 0;
}