浅学竞赛图

wjyppm1403 · 2025-07-17 12:00:42 · 算法·理论

可能更好的阅读体验

1. 定义

竞赛图，即任意两点之前有且仅有一条边的有向图。即有向完全图，有 \dbinom{n}{2} 条边。

至于为什么叫竞赛图，就是赢得点向输的点连边，一个边代表的是胜负关系。

2. 性质

兰道定理（竞赛图判定）

我们定义比分序列为将每个点的出度 s_{i} 从小到大排序的序列。

那么若满足 \sum\limits_{i=1}^k s_{i}\ge \dbinom{k}{2} 且当 k=n 时取等（即 \sum\limits s=\dbinom{n}{2}），则一定能够造出一种竞赛图，反之不能。

必要性显然，考虑充分性证明，我们构造初始图，对于 j<i 则 i\to j 连边，设此时比分序列为 a，这个序列显然在上述条件能够取到等号。保持 \sum\limits_{i=1}^k a_{i}\le \sum\limits_{i=1}^k s_{i}，不断调整图直到 a=s。

未构造完成时开头必然是一段等于后面接一个 a_{l}<s_{l}，为了让后面的方法修改后使得 a 仍然有序，我们找到最后一个 a_{l}=a_{u} 的 u，显然有 a_{u}<s_{u}。因为总和固定，必然能找到第一个 v 使得 a_{v}>s_{v}。

此时有 a_{u}<s_{u}\le s_{v}<a_{v}，有 a_{v}\ge a_{u}+2。

当 \exists v \to u，考虑翻转这条边，否则必然存在 p 使得 v \to p \to u，那么把路径反转。因为 a_{u}<s_{u},a_{i}\le s_{i},\forall i \in (u,v)，不难证明反转后的序列仍然保持性质（\sum\limits a \le s）这样构造下去一定有解。

注意，这里定理都是存在，对于同一个比分序列可能对应本质不同的竞赛图。

兰道定理实质

兰道定理的实质是在一个序列和一定时，可以对于任意两个有关系（边）的位置进行相等量的调整（s_{i}\leftarrow s_{i}+v,s_{j}\leftarrow s_{j}-v），那么要判定任意一个值的序列是否与序列值的下界形式一样时，只需要判断是否每个前缀和都大于等于下界，以及最后的和与预期相等即可。证明考虑构造法不断调整。

竞赛图强连通分量个数（推论）

即：

其中 s 还是比分序列。证明如下：

竞赛图有个很好的性质：一定存在一条哈密尔顿路径。

考虑设 f(i,j) 表示 i 个点，最长路径为 j 的竞赛图数量。

显然有 f(i,i) 为强连通竞赛图，但是这里我们可以不用像上面不知名题求，就用容斥 f(i,i)=2^{\frac{i(i-1)}{2}}-\sum\limits_{j=1}^{i-1} f(i,j) 即可。

考虑 f(i,1) 可以构造出所有 1 号点的边连向 1 号点即可，有 f(i,1)=2^{\frac{(i-1)(i-2)}{2}}。

那么剩下的怎么求，考虑将图划分为两个块，一个块是供 1 走的块，剩下的块不给 1 走，但是可能不存在不给 1 走的块。

那么有 f(i,j)=f(j,j) \times \binom{i-1}{j-1} \times 2^{\frac{(i-j)(i-j-1)}{2}}，考虑 j 个点连通块的连边方式，让后要选点，在把剩下的连边即可。

时间复杂度 O(n^2)，但是可怕的是 BZOJ 挂了，有谁好心传个原题？

CF913F

令 p=\dfrac{a}{b}。

考虑倒推答案，设 f(i) 表示 i 个点的期望答案，g(i) 表示形成大小为 i 的 SCC 概率，h(i,j) 表示 i 个人打比赛，其中 j 个人被 (i-j) 个人打赢的概率。

最后一个 SCC 的大小，有：

但是 f(i) 会转移到自己，要解方程，这里不过多叙述。

考虑 g_{i} 如何求，考虑只要图中没有点被其它点都吊打的情况它就是强联通图，那么转移：

考虑 h，对于新加入一个点，如果在 j 中那么输给 i-j，反之要赢 j 个点，那么有：

时间 O(n^2)。

UOJ961 赛场设计

如何判断一个图是不是好图？你发现首先这个图一定是一个 DAG；其次考虑建出其不可达关系图，我们会发现这个图比竞赛图还密集，一些竞赛图的结论在这个图上仍然成立：

• 缩点后是一条链。
• 任意一个 SCC 大小不超过 3。

我们可以考虑 DP 求解，设 f(i,j) 表示考虑到 i 个点最后一个 SCC 大小为 j 的方案数。

有转移：

初始化 f(1,1)=\dbinom{n}{1},f(2,2)=\dbinom{n}{2}。时间复杂度 O(n)。

3.2 SCC 及其拓展

CF1268D

两个结论：

• 对于 n\ge 4，n 阶强联通竞赛图具有 n-1 阶强联通子图。
• 对于 n\ge 7，n 阶竞赛图存在一种翻转方案使得只需要翻转一个结点就能让它强联通。

对于 n\le 6，暴力枚举翻转结点即可，对于 n>6 考虑枚举每个位置翻转并检查就好了。我们可以用兰顿定理的推论（上面有讲）来快速判断是否强连通。

证明可以看其他题解：题解 CF1268D 【Invertation in Tournament】

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=2520,MOD=998244353;
int n,cf[MN],h[MN];
bool mp[MN][MN];

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

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            char c;
            cin>>c;
            mp[i][j]=c-'0';
            h[i]+=mp[i][j];
        }
    }
    for(int i=1;i<=n;i++) cf[i]=h[i];
    if(check()){
        cout<<"0 1";
        return 0;
    }
    int ret=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cf[j]=h[j]; 
        for(int j=1;j<=n;j++){
            cf[i]-=mp[i][j]*2-1;
            cf[j]+=mp[i][j]*2-1;
        }
        if(check()) ret++;
    }
    if(ret){
        cout<<1<<" "<<ret;
        return 0;
    }
    if(n==4) cout<<-1;
    if(n==6) cout<<"2 18";
    return 0;
}

P3561 [POI 2017] Turysta

定理上面都讲完了，先缩点，然后对于每个强连通分量，求哈密顿回路。然后就可以对任意一个强连通分量任意点进，任意点出了。

怎么构造可以去看其他题解的构造。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=2e3+15;
int n,tcnt,nxt[MN],a[MN][MN],in[MN],tpos[MN],pos[MN];
vector<int> adj[MN],G[MN],dcc[MN],ans[MN];

namespace Tarjan{
    int dfn[MN],low[MN],s[MN],col[MN],ctot,top,dtot;
    bool vis[MN];

    void tarjan(int u){
        low[u]=dfn[u]=++dtot;
        s[++top]=u;
        vis[u]=1;
        for(auto v:adj[u]){
            if(!dfn[v]){
                tarjan(v);
                low[u]=min(low[u],low[v]);
            }else if(vis[v]){
                low[u]=min(low[u],dfn[v]);
            }
        }
        if(low[u]==dfn[u]){
            ctot++;
            int p;
            do{
                p=s[top--];
                col[p]=ctot;
                vis[p]=0;
            }while(p!=u);
        }
    }
}using namespace Tarjan;

void toposort(){
    queue<int> q;
    for(int i=1;i<=ctot;i++){
        if(!in[i]) q.push(i);
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        tpos[++tcnt]=u;
        pos[u]=tcnt;
        for(auto v:G[u]){
            in[v]--;
            if(!in[v]) q.push(v);
        }
    }
}

void getham(int c){
    if(dcc[c].size()==1) return;
    int s=dcc[c][0],t=s;
    for(int i=1;i<dcc[c].size();i++){
        int x=dcc[c][i];
        if(a[t][x]) nxt[t]=x,t=x;
        else if(a[x][s]) nxt[x]=s,s=x;
        else{
            for(int j=s;j!=t;j=nxt[j]){
                if(a[j][x]&&a[x][nxt[j]]){
                    nxt[x]=nxt[j];
                    nxt[j]=x;
                    break;
                }
            }
        }
    }
    t=0;
    for(int i=nxt[s];i;i=nxt[i]){
        if(t){
            if(a[i][s]){
                t=i;
                continue;
            }
            for(int j=s,k=nxt[s];j!=t;j=k,k=nxt[k]){
                if(a[i][k]){
                    nxt[j]=nxt[t];
                    nxt[t]=s;
                    s=k;
                    t=i;
                    break;
                }
            }
        }else if(a[i][s]) t=i;
    }
    nxt[t]=s;
}

int main(){
    cin>>n;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i-1;j++){
            int x;
            cin>>x;
            if(x){
                adj[j].push_back(i);
                a[j][i]=1;
            }else{
                adj[i].push_back(j);
                a[i][j]=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) Tarjan::tarjan(i);
    }
    for(int i=1;i<=n;i++){
        dcc[col[i]].push_back(i);
    }
    for(int u=1;u<=n;u++){
        for(auto v:adj[u]){
            if(col[u]!=col[v]){
                G[col[u]].push_back(col[v]);
                in[col[v]]++;
            }
        }
    }
    toposort();
    for(int i=1;i<=tcnt;i++){
        getham(tpos[i]);
    }
    for(int i=1;i<=n;i++){
        int lst=i,now=pos[col[i]];
        while('QWQ'){
            if(dcc[tpos[now]].size()==1){
                ans[i].push_back(lst);
                if(now==tcnt) break;
                lst=dcc[tpos[++now]][0];
                continue;
            }
            ans[i].push_back(lst);
            for(int j=nxt[lst];j!=lst;j=nxt[j]){
                ans[i].push_back(j);
            }
            if(now==tcnt) break;
            lst=dcc[tpos[++now]][0];
        }
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i].size()<<' ';
        for(auto p:ans[i]) cout<<p<<" ";
        cout<<'\n';
    }
    return 0;
}

4. 参考

• 竞赛图的一些性质 - _zwl - 博客园
• 【CF913F】Strongly Connected Tournament - heyujun - 博客园
• 竞赛图专题突破 - Compound_Interest - 博客园
• 由竞赛图的分数序列构造出竞赛图 - yspm - 博客园
• 竞赛图小记 - 洛谷专栏