题解 CF1268D 【Invertation in Tournament】

Caro23333 · 2020-02-17 18:43:48 · 题解

Update: 添加了代码。

我先谢个罪，提交翻译的时候没看到竞赛图的条件，如果您看了我的错误题意耽误了时间，非常非常抱歉qaqqqqq 正确题意见讨论区

这题真的是很美妙了。不想看长篇证明的选手可以只看粗体字。

引理：对于n\ge 4，n阶强连通竞赛图存在n-1阶强连通子图。

引理的证明：

考虑当前已有一个n-1阶竞赛图G，在其中新添一个编号为n的点和一些有向边，得到一个n阶竞赛图G'。

对G求出所有的强连通分量并缩点，得到有向无环图S。对S的点集拓扑排序，得到顶点序列\{a\}=a_1,a_2,\dots,a_k。作如下分类讨论:

• k=1

  这意味着G是强连通的，直接得证。

• k\ge 3

  由于G'是强连通的，这意味着从a_k存在一条路径到达a_1。

  根据拓扑序的关系，必然存在u\in a_k,v\in a_1，G中有边(u,n)和(n,v)。又因G是竞赛图，从而对任意x\in a_i, y\in a_j且i<j，G中都有边(x,y)。

  于是我们任意挖去顶点u\in a_m，其中1<m<k。对于任意顶点对(x,y)(x<n, y<n, x\neq u, y\neq u)，存在路径如\{x,a_k,n,a_1,y\}。若x,y中有n同理。

  也就是说，任意两点之间都可以互相到达。于是，去掉u之后的图不仅是G的子图，也是一个n-1阶强连通图。

• k=2

  同理，G中有边(u,n)和(n,v)，其中u\in a_1,v\in a_2。

  但如果我们随意选取一个强连通分量并且拿走其中一个点，可能使得上式中唯一满足要求的u（或者v）被删除，这样的话图中就不再有环了。

  此时运用n\ge 4的性质，可以发现a_1,a_2中至少一个的点数是大于等于2的，不妨设为a_2。那么我们只要保证拿去的点不是v，就一定可以使图中仍存在\{a_2,n,a_1\}的路径。这样的话，不难发现剩下的图仍是强连通的。

引理得证。

引理之推论：对于n\ge 4的强连通竞赛图，总可以翻转恰好一个点，使得它还是强连通的。

由引理易得，翻转多出来那个点就可以了。下面是核心结论。

定理：n>6时，总可以通过翻转至多1个点使得原图变成强连通的。

证明：

还是熟悉的配方，设原图G缩点并拓扑排序之后得到\{a\}=a_1,a_2,\dots,a_k。

• k=1

  不需要翻转。

• k\ge 3

  任取u\in a_m进行翻转，其中1<m<k。对于任意顶点对(x,y)，都有路径\{x,a_k,u,a_1,y\}，从而翻转u之后原图变为强连通的。

• k=2

  由于n>6，则a_1,a_2中必存在至少一者点数大于等于4，不妨设为a_1。

  因为点集a_1在G中对应的子图G'是一个强连通竞赛图，从而根据引理的推论，G'有一顶点u，使得翻转u之后，a_1对应的子图仍是强连通竞赛图。

  翻转如上的u之后，应该存在一条从a_2某一点指向u的边。同时因为|a_1|\ge 4，应该还保留从a_1指向a_2的边。也就是说，形成了一个包含a_1,a_2的环。

  又因为a_1对应的子图在翻转之后仍是强连通的，从而现在整个图是强连通的。

定理得证。

这样的话，对于n\le 6我们可以暴力枚举翻转的点的集合并且判断，n>6时只需要枚举翻转了哪个点，再进行判断即可。

最后一个问题是，如果直接用tarjan进行强连通的判断，单次是O(n^2)的，不可承受。

观察发现，如果将一个竞赛图缩点并拓扑排序，并且设拓扑序最后的SCC中点数为k，那么这个SCC中所有的点出度之和为\binom{k}{2}。此外，还能发现这些点的出度都比SCC外的任意一点出度要小。由此我们不难得到一个结论：

对于一个竞赛图，将其顶点按出度从小到大排序，则存在k<n使得前k个顶点的出度之和等于\binom{k}{2}是该竞赛图非强连通的充要条件。

限于体力和篇幅，证明留做习题。

这样，我们可以在O(n\log n)的时间内完成单次判断，总的时间复杂度就是O(n^2\log n)。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;
typedef long long ll;
const int MAXN = 2005;
char str[MAXN];
int n,G[MAXN][MAXN],H[MAXN][MAXN],deg[MAXN],tdeg[MAXN];
inline bool check()
{
    sort(tdeg+1,tdeg+n+1);
    int sum = 0;
    for(int i = 1; i<n; i++) 
    {
        sum += tdeg[i];
        if(sum==i*(i-1)/2)
            return false;
    }
    return true;
}
inline int count(int x)
{
    int res = 0;
    for(; x; x -= x&-x)
        res++;
    return res;
}
inline void reverse(int x)
{
    for(int i = 1; i<=n; i++)
        if(i!=x)
            G[x][i] ^= 1, G[i][x] ^= 1;
}
inline void solve1()
{
    int ans = 1<<30, cnt = 0;
    for(int st = 1; st<(1<<n); st++)
    {
        for(int i = 1; i<=n; i++)
            if(st&(1<<(i-1)))
                reverse(i);
        memset(tdeg,0,sizeof(tdeg));
        for(int i = 1; i<=n; i++)
            for(int j = 1; j<=n; j++)
                tdeg[i] += G[i][j];
        if(check())
        {
            int c = count(st);
            if(c<ans)
                ans = c, cnt = 1;
            else if(c==ans)
                cnt++; 
        }
        for(int i = 1; i<=n; i++)
            if(st&(1<<(i-1)))
                reverse(i);
    }  
    if(cnt)
    {
        for(int i = 1; i<=ans; i++)
            cnt *= i;
        cout << ans << " " << cnt << endl;
    }
    else
        cout << -1 << endl;
} 
inline void reverse1(int x)
{
    tdeg[x] = n-deg[x]-1;
    for(int y = 1; y<=n; y++)
        if(y!=x)
        {
            tdeg[y] -= G[y][x];
            G[x][y] ^= 1, G[y][x] ^= 1;
            tdeg[y] += G[y][x];
        }
}
inline void solve2()
{
    int cnt = 0;
    for(int i = 1; i<=n; i++)
    {
        memcpy(tdeg,deg,sizeof(deg));
        reverse1(i);
        cnt += check();
        reverse1(i);
    }
    cout << 1 << " " << cnt << endl;
}

int main()
{
    cin >> n;
    for(int i = 1; i<=n; i++)
    {
        cin >> str+1;
        for(int j = 1; j<=n; j++)
            deg[i] += G[i][j] = str[j]-'0';
    }
    memcpy(tdeg,deg,sizeof(deg));
    if(check())
    {
        cout << 0 << " " << 1 << endl;
        return 0;
    }
    if(n<=6)
        solve1();
    else
        solve2();
    return 0;
}