C 萌新向题解二分图匹配与竞赛图综合题

题目链接

经验教训 ：

• 题中要求了 $i,i+ni,i+n$ 之间没有边也就是转化形成的图是竞赛图且没有自环；
• 要仔细看题 题中明确给出了是有 $n\cdot (n-1)÷2n\backslash cdot(n-1)\; \backslash div2$ 条边

相关前置知识

• 完全图 是指每个顶点都和其他所有点有直接边相连的图；
• 竞赛图就是有向完全图；
• $nn$ 阶图是指图中有 $nn$ 个点；
• 竞赛图一定是连通的，但不一定是强连通的；
• 若竞赛图中包含环，那么图中至少包含三个点，即不存在二元环；
• 哈密顿路径是指每个点都只经过一次的路径
• 强连通分量是极大强连通子图；
• 竞赛图必然存在哈密顿路径；
• 图中存在哈密顿路径的充分必要条件是 图是连通的；
• 图上孤立(出度和入度都是 $00$ )的点也算一个连通分量

思路

• 将 $i,n+ji,n+j$ 之间有边看作是 $i\to ji\backslash to\; j$ 的有向边，二分图就变成 $nn$ 阶有向完全图即竞赛图
• 即给出的二分图的最大匹配数的最小值是 $n-1n-1$ .
  • 证明如下 假设哈密顿路径是 $a_1\to a_2\to a_3\to a_4\to a_i\to \mathrm{.}\mathrm{.}\mathrm{.}\to a_{n}a\_1\; \backslash to\; a\_2\; \backslash to\; a\_3\; \backslash to\; a\_4\; \backslash to\; a\_i\; \backslash to...\backslash to\; a\_n$
  • 则有如下 $n-1n-1$ 个匹配 $a_1\to a_2+n,a_2\to a_3+n,\mathrm{.}\mathrm{.}\mathrm{.},a_{n-1}\to a_n+na\_1\; \backslash to\; a\_2\; +\; n,\; a\_2\; \backslash to\; a\_3+n,...,\; a\_\{n-1\}\backslash to\; a\_n+n$
• 如果最大匹配数是$nn$ ,则形成的竞赛图中所有的强连通分量是有环的；
  • 因为每一个点都有后继节点，最后会形成若干个环；
  • 每个环是强连通分量；

结论 如果在形成的竞赛图中每一个强连通分量中点的个数都大于 $11$ （至少为 $33$ ）则能形成完美匹配

否则答案为 $n-1n-1$

利用$\mathtt{\text{Tarjan}}\backslash texttt\{Tarjan\}$ 算法实现强连通分量的寻找。

``

const int N= 3e3+2;
int dfn[N],low[N],timestamp;
bool in_stack[N];
bool flag = true;
int stk[N], top;
// scc 是强连通分量的英文缩写
int scc_cnt = 0;
int Size[N];
// 邻接表
vector<int> G[N];

void tarjan(int u){
    stk[++top] = u;
    in_stack[u] = true;
    low[u] = dfn[u] = ++timestamp;
    for(auto v : G[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(in_stack[v]){
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(low[u] == dfn[u]){
        ++scc_cnt;
        int v;
        do{
            Size[scc_cnt]++;
            v = stk[top--];
            in_stack[v] = false;
        }while(u !=v);
    }
}

void solve(){
    int n; cin >> n;
    for(int i =1; i <= n; i++){
        for(int j =1; j <= n; j++){
            int e; cin >> e;
            if(e){
                G[i].push_back(j);
            }
        }
    }
    // 求强连通分量
    for(int i =1; i<=n; i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    for(int i =1; i <= scc_cnt; i++){
        if(Size[i] < 2){
            flag = false;
            break;
        }
    }
    if(flag) cout << n ;
    else cout << n-1;
}

也可以使用兰道定理

兰道定理： 一个有向完全图(竞赛图)是强连通的充分必要条件是

将每个点的入度按从小大到排序形成序列$d_{i}d\_i$

对任意的$1\le k\le n-11\backslash le\; k\; \backslash le\; n-1$

${\sum }_{i=1}^k{d}_i=\left(\genfrac{}{}{0px}{}{k}{2}\right)\backslash sum\_\{i\; =\; 1\}^\{k\}d\_i\; =\; \backslash binom\{k\}\{2\}$

都不成立