2023牛客暑期多校训练营5-C Cheeeeen the Cute Cat
https://ac.nowcoder.com/acm/contest/57359/C
文章目录
- 2023牛客暑期多校训练营5-C Cheeeeen the Cute Cat
- 题意
- 解题思路
- 兰道定理：
- 代码
题意
解题思路
可以将边 ( i , j + n ) (i,j+n) (i,j+n)转变成 ( i , j ) (i,j) (i,j)连边，将二分图转变为竞赛图（由题意可知没有重边， n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n−1)条边恰好等于一个 n n n个点的竞赛图边数）。根据题意，在二分图上进行完美匹配等价于求对应竞赛图的哈密顿回路：将 ( a 1 , a 2 + n ) 、 ( a 2 , a 3 + n ) 、 ( a 3 , a 4 + n ) 、 ( a 4 , a 5 + n ) ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ( a k , a 1 + n ) (a_1,a_2+n)、(a_2,a_3+n)、(a_3,a_4+n)、(a_4,a_5+n)······(a_k,a_1+n) (a1,a2+n)、(a2,a3+n)、(a3,a4+n)、(a4,a5+n)⋅⋅⋅⋅⋅⋅(ak,a1+n)转变为 a 1 ⟶ a 2 ⟶ a 3 ⟶ a 4 ⟶ a 5 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ a k ⟶ a 1 a_1\longrightarrow a_2\longrightarrow a_3\longrightarrow a_4\longrightarrow a_5······a_k\longrightarrow a_1 a1⟶a2⟶a3⟶a4⟶a5⋅⋅⋅⋅⋅⋅ak⟶a1。
每个 n ≤ 3 n\le 3 n≤3的强连通分量都有哈密顿回路，若该图中都是这种强连通分量,就能找出一条长为 n n n的哈密顿回路，若有孤立的强连通分量，就会有 1 1 1个点无法匹配。
对于一个强连通图显然可以全部匹配，则答案为 n n n，只需特判孤立的强连通分量即可，若有，则答案为 n − 1 n-1 n−1。
兰道定理：
一个竞赛图强连通的充要条件是：把它的所有顶点按照出度d从小到大排序，对于任意k∈[0,n−1]
都不满足 ∑ i = 0 k d i = ( k + 1 2 ) \sum_{i=0}^k di=\dbinom {k+1}2 ∑i=0kdi=(2k+1)。
根据兰道定理，可以根据出度序列判断强连通分量。（当然也可以尝试 t a r j a n tarjan tarjan水过去。）
代码
#include<bits/stdc++.h>
using namespace std;
int n,deg[3003],a;
int main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a;if(a)deg[a]++;}}sort(deg+1,deg+n+1);int s=0;for(int i=1,j=0;i<=n;i++){s+=deg[i];if(s==i*(i-1)/2){if(i-j<3){cout<<n-1;return 0;}j=i;}}cout<<n;
}
![[SQL挖掘机] - 窗口函数 - lead](/images/no-images.jpg)
