题解 CF1268D【Invertation in Tournament】

· · 题解

CF1268D Invertation in Tournament解题报告：

更好的阅读体验

题意

给定一个 n 个点的竞赛图，定义一次翻转操作为翻转一个结点相连的所有边方向，求至少要翻转多少个结点才能让图强联通，并求出最少操作的方案数。（3\leqslant n\leqslant 2000）

分析

妙妙题+竞赛图综合运用题。

orz Caro23333，这篇题解就是把他的题解复述一遍（。

我们有两个结论。（结论都放到后面证明）

结论 1：对于 n\geqslant 4，n 阶强联通竞赛图具有 n-1 阶强联通子图。

结论 2：对于 n\geqslant 7，n 阶竞赛图存在一种翻转方案使得只需要翻转一个结点就能让它强联通。

那么对于 n\leqslant 6，我们暴力枚举翻转的结点检查，对于 n>6，我们枚举每个位置翻转并检查就好了。

发现翻转点之后缩点太慢，可以使用兰道定理来快速判断是否是强联通。

兰道定理：一个序列 s 为一个合法的出度序列当且仅当 s 排序后满足：

\forall_{1\leqslant k\leqslant n}\sum_{i=1}^ks_i\geqslant {k\choose 2}

这样我们把更新后的出度排一遍序，如果它不是强联通，那么缩点之后最后一个强联通块的出度一定是最小的若干个，我们检查是否存在 1\leqslant k<n 满足 \sum_{i=1}^k s_i={k\choose 2} 就好了。

时间复杂度：O(n^2\log n)。

代码

注意，翻转是有顺序的，所以 n\leqslant 6 的时候选择顶点的方案数要乘上顶点数的阶乘。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=2005;
int n,ans1,ans2;
int a[maxn][maxn],deg[maxn],d[maxn];
string s;
inline int modify(int x,int y){
    deg[x]-=a[x][y],a[x][y]^=1,deg[x]+=a[x][y];
}
int check(){
    for(int i=1;i<=n;i++)
        d[i]=deg[i];
    sort(d+1,d+1+n);
    int sum=0;
    for(int i=1;i<n;i++){
        sum+=d[i];
        if(sum==i*(i-1)/2)
            return 0;
    }
    return 1;
}
void solve1(){
    ans1=n+1;
    for(int i=0;i<(1<<n);i++){
        int tot=0;
        for(int j=1;j<=n;j++)
            if((i>>(j-1))&1){
                tot++;
                for(int k=1;k<=n;k++)
                    modify(j,k),modify(k,j);
            }
        if(tot<=ans1&&check()){
            if(tot==ans1)
                ans2++;
            if(tot<ans1)
                ans1=tot,ans2=1;
        }   
        for(int j=1;j<=n;j++)
            if((i>>(j-1))&1)
                for(int k=1;k<=n;k++)
                    modify(j,k),modify(k,j);
    }
    for(int i=1;i<=ans1;i++)
        ans2*=i;
}
void solve2(){
    ans1=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            modify(j,i),modify(i,j);
        if(check())
            ans2++;
        for(int j=1;j<=n;j++)
            modify(j,i),modify(i,j);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        cin>>s;
        for(int j=1;j<=n;j++)
            a[i][j]=s[j-1]-48,deg[i]+=a[i][j];
    }
    if(check()){
        puts("0 1");
        return 0;
    }
    if(n<=6)
        solve1();
    else solve2(); 
    if(ans1>n)
        puts("-1");
    else printf("%d %d\n",ans1,ans2);
    return 0;
}

结论的证明

不想写，咕了。

可以参考这两篇文章的证明：

题解 CF1268D 【Invertation in Tournament】

[竞赛图判定定理]兰道定理(Landau's Theorem)介绍及其一种证明