每日一题：竞赛图

题目

给定一个 $n$ 元有向完全图，每次操作可以翻转一条边。求最少的操作次数，使得图中不存在三元环。$(n <= 10)$

Solution

Code

#include <algorithm>
#include <iostream>
using namespace std;
int n, pre[20];
char s[20][20];
int main() {
  while (cin >> n) {
    for (int i = 0; i < n; i++) cin >> s[i], pre[i] = i;
    int res = 1e9;
    do {
      int sum = 0;
      for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) sum += s[pre[j]][pre[i]] & 1;
      res = min(res, sum);
    } while (next_permutation(pre, pre + n));
    cout << res << endl;
  }
  return 0;
}