「CF1268D」Invertation in Tournament

发表于 分类于

题目链接：https://codeforces.com/contest/1268/problem/D。

太棒了，学到许多（？）

首先如果整个图是$\rm SCC$答案是$0$。

如果图是由$\geqslant 3$个$\rm SCC$组成的，因为竞赛图缩点之后会是个链状的东西，也就是每个点连向后面所有点的形状，所以如果我们反转中间的$\rm SCC$的任意一个点，假设头尾是$h,t$，反转的点是$u$，那么可以得到一个这样的环：$h\to t\to u\to h$，那么这种情况只需要一次操作。

有一个结论是说，一个竞赛图如果强连通，那么一定可以找到一个长度为$n-1$的环，因为我们把一个点去掉之后，会剩下一个链，可以发现我们可以在这个链上去掉一个点他还是一个链。

所以如果是$2$个$\rm SCC$，并且如果有一个大小$\geqslant 4$，那么可以找到一个点使得翻转之后大的$\rm SCC$还是$\rm SCC$，那么这个时候两个$\rm SCC$会强连通，所以也只需要一次操作。

综上如果这个图$n>6$，一定只需要$\leqslant 1$次操作。

有一个小技巧是说，注意到竞赛图缩点之后是条链，那么链的最后一个点是没有出边的，而且这些点是按出度排好的，所以我们如果反过来，按出度排序，如果有一个$x$满足$\sum_{i=1}^{x}d_i=x(x-1)/2$就说明这些点是最后一个$\rm SCC$，如果$x\ne n$就说明这个图不强连通，否则一定强连通。

所以如果$n\leqslant 6$就爆搜，否则枚举每个点然后判断，复杂度$O(n^2\log n)$。（排序可以换成桶排然后少一个$\log$）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define data asd09123jdf02i3h

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 2e3+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int e[maxn][maxn],d[maxn],n,ans,a[maxn];
char s[maxn];

int check() {
    for(int i=1;i<=n;i++) a[i]=d[i];
    sort(a+1,a+n+1);
    for(int i=1;i<n;i++) {
        a[i]+=a[i-1];
        if(a[i]==i*(i-1)/2) return 0;
    }return 1;
}

void invert(int x) {
    for(int i=1;i<=n;i++)
        if(i!=x) {
            d[x]-=e[x][i],d[i]-=e[i][x];
            swap(e[x][i],e[i][x]);
            d[x]+=e[x][i],d[i]+=e[i][x];
        }
}

void dfs(int x,int m) {
    if(x==m+1) return ans+=check(),void();
    for(int i=1;i<=n;i++) invert(i),dfs(x+1,m),invert(i);
}

int main() {
    read(n);
    for(int i=1;i<=n;i++) {
        scanf("%s",s+1);
        for(int j=1;j<=n;j++) e[i][j]=s[j]-'0',d[i]+=s[j]-'0';
    }
    if(check()) return puts("0 1"),0;
    if(n<=6) {
        for(int i=1;i<=6;i++) {
            dfs(1,i);
            if(ans) return printf("%d %d\n",i,ans),0;
        }puts("-1");
        return 0;
    }
    for(int i=1;i<=n;i++) invert(i),ans+=check(),invert(i);
    printf("1 %d\n",ans);
    return 0;
}