竞赛图
定义与若干性质
定义 1.1
竞赛图是简单有向图，满足任意两点之间都有且仅有一条边。
性质 1.1
竞赛图缩点之后的任唯一拓扑序是全序集。
证明：
设竞赛图 \((V,E)\)。
显然，若点 \(u,v\) 不在同一个强连通分量，在新图上随意指定 dfs 序 \(t\)。根据竞赛图，若 \(t(u)<t(v)\)，那么一定有 \((u,v)\in E\)，因此 \(t\) 是全序的。
值得一提的是，这证明缩点之后是“链加上一些前向边”。以下，我们认为“左边”是拓扑序更小的那一端，“中间的”是非最左最右的点。
定理 1.1 Camion-Moon 定理
强连通竞赛图有哈密尔顿环。
证明：
我们归纳构造这个哈密尔顿环。
\(|V|=1\) 显然成立。
否则，删去任意点 \(x\)，会分出若干强连通分量，根据性质 1.1，这些强连通分量“成链”。
根据归纳假设，这些强连通分量内部有哈密尔顿环。“合并”这些环得到删去 \(x\) 后的图的“从左到右”的哈密尔顿路。
根据原图是强连通图， \(x\) 连向最左的强连通分量，最右的连向 \(x\)。这样合并进 \(x\) 就得到了哈密尔顿环。
如果只有缩出来一个强连通分量，环一定能够有一个地方插的进去 \(x\)。
算法 1.1
\(O(n^2)\) 求强连通竞赛图哈密尔顿环。
上述构造方法的实现是 \(O(n^3)\) 的（至少我不知道更少的做法）。
首先容易找到哈密尔顿路：增量插入即可。
首先找到第一个连向起点的点，令起点为 \(S\)，此点为 \(T\)，对于接下来的每个点 \(i\)，找到它连向前面的第一个点 \(x\)，现在环是 \(i\to x_2\to T\to S\to x_2\text{前一个点}\)。所以令 \(T\to S,i\to T\)。
这是它的实现。（P3561）
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+5;
int n,low[maxn],dfn[maxn],bel[maxn],st[maxn],vis[maxn],tp=0,T=0,cnt=0;
vector<int> pt[maxn],ans[maxn];
int d[maxn][maxn],nxt[maxn];
void tarjan(int u){
dfn[u]=low[u]=++T,st[++tp]=u,vis[u]=1;
for(int v=1;v<=n;v++){
if(!d[u][v])continue;
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]){
++cnt;
while(1){
int x=st[tp--];
pt[cnt].push_back(x);
bel[x]=cnt,vis[x]=0;
if(x==u)break;
}
}
}
void solve(int a){
if(pt[a].size()==1)return ;
int s,t,x;
s=t=pt[a][0];
for(int i=1;i<pt[a].size();i++){
x=pt[a][i];
if(d[t][x]){
nxt[t]=x;t=x;
continue;
}
if(d[x][s]){
nxt[x]=s;s=x;
continue;
}
for(int j=s;j!=t;j=nxt[j]){
if(d[j][x]&&d[x][nxt[j]]){
nxt[x]=nxt[j],nxt[j]=x;
break;
}
}
}//Hamilton path
t=0;
for(int i=nxt[s];i;i=nxt[i]){
if(d[i][s])t=i;
else if(t){
for(int j=s;j!=t;j=nxt[j]){
if(d[i][nxt[j]]){
x=nxt[j];nxt[j]=nxt[t],nxt[t]=s;
s=x,t=i;
break;
}
}
}
}//Hamilton circle
nxt[t]=s;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
int x;cin>>x;
if(x)d[j][i]=1;
else d[i][j]=1;
}
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=cnt;i++)solve(i);
int x,k;
for(int i=1;i<=n;i++){
x=i,k=bel[i];
while(1){
ans[i].push_back(x);
if(pt[k].size()==1){
if(k==1)break;
--k,x=pt[k][0];
continue;
}
for(int j=nxt[x];j!=x;j=nxt[j])ans[i].push_back(j);
if(k==1)break;
k--,x=pt[k][0];
}
cout<<ans[i].size()<<" ";
for(auto u:ans[i])cout<<u<<" ";
cout<<endl;
}
return 0;
}
定理 1.2 Redei 定理
竞赛图有哈密尔顿路。
同上证明。
性质 1.2
一个有向图 \(G\) 是泛圈的，当且仅当 \(\forall i\in[3,n]\cap\Z\)，\(G\) 有 \(i\) 元环。
强连通竞赛图是泛圈的。
证明：
显然 \(n\le 3\) 成立。
只需证明：\(\forall n\ge 4\)，\(n\) 阶竞赛图有 \(n-1\) 元环。
类似于上面的构造，如果链上的这些强连通分量大小有一个大于一就绕过他的一个点，显然是可行的。
否则，强连通分量大小均为一，显然我可以跨过链上来越过一个点。
定理 1.3 Landau 定理
给定一不降序列 \(\{p_i\}^n_{i=1}\)，满足
\[\sum p_i=\binom n 2 \]存在一竞赛图使得节点出度序列为 \(p\) 的充要条件是
\[\forall i\in [1,n]\cap\Z,\sum_{j=1}^ip_j\ge \binom i2 \]证明：
必要性显然，下证明充分性，即可以构造出这样的竞赛图。
首先设初始竞赛图为 \((V=[1,n]\cap\Z,E=\{(i,j)\mid i>j\})\)，这样的出度序列 \(q\) 满足
\[\forall i\in [1,n]\cap\Z,\sum_{j=1}^iq_j= \binom i2\le \sum_{j=1}^ip_j \]调整过程中，这个条件将一直被满足。
找到最小的 \(x\) 满足 \(q_x<p_x\)（找不到就完成了），最小的 \(y\) 满足 \(q_y>p_y\)（显然其存在且 \(>x\)）。
一定有 \((y,x)\in E\)，或 \(\exists a,(y,a),(a,x)\in E\)。此时，反转任意一个这样的边一次。
以上操作显然不破坏性质。一直做去，有限次就能得到正确结果。
性质 1.3
给定竞赛图不降出度序列 \(\{p_i\}_{i=1}^n\)，其强连通分量个数为
\[\sum_{i=1}^n\left[\left(\sum_{j=1}^i p_j \right)=\binom i2\right] \]证明：
首先证明其大于等于强连通分量个数。
缩点后图成链，显然，靠左的强连通分量中每个点的出度都比靠右的强连通分量里任意点的出度大。
那么显然，对于每个非最右强连通分量，
\[\exists i,\sum_{j=1}^i p_j=\binom{i}2 \]且 \(p_1\sim p_i\) 和每个靠右的强连通分量里面的点对应。
显然 \(i\) 是不同的，以及 \(i=n\) 也满足这个，就证明了其大于等于强连通分量个数。
然后证明其小于等于强连通分量个数。
\[\sum_{j=1}^i p_j=\binom{i}2 \]对于所有此式成立的 \(i<n\)， \(p_1\sim p_i\) 不向外连边，所以有 \(p_{i+1}\sim p_n\) 代表的节点每个都向 \(p_1\sim p_i\) 代表的节点的每个连边。
所以这样的 \(i\) 被强连通分量的边界对应。还有 \(i=n\)。这样就证明了其小于等于强连通分量个数。
证毕。
算法 1.2
无权竞赛图最小割。
设目前左右集合为 \(S,T\)，初始 \(S=\{s\},T=V-\{s\}\)。
考虑把 \(u\) 从 \(T\) 换到 \(S\) 的变化量 \(\Delta\)。
\[\Delta=\sum_{i\in T}[(u,i)\in E]-\sum_{i\in S}[(i,u)\in E]\\ =\left(\sum_{i=1}^n[(u,i)\in E]\right)-|S|\\ =p_u-|S| \]因此只需加入一段按 \(p\) 排序后前缀即可。
具体地，记
\[s_i=\sum_{j=1}^i p_j-j,s_0=0 \]其中 \(p\) 升序排序，且去除 \(s,t\)。
答案即为 \(\min s_i+p_s\)。
具体来说，我们可以依据 \(s,t\) 对 \(p\) 分段，然后求解 RMQ 问题。
可以 \(O(n\log n)-O(1)\) 在线回答。
例题：CF1268D
引理 2.1
\(n(n\ge 4)\) 阶强连通竞赛图有 \(n-1\) 阶强连通导出子图。
证明：
随意取一个点 \(x\)，设删去之后缩点从左到右为 \(H_1\sim H_k\)。
如果 \(k=1\)，即证。
否则，如果所有 \(|H_i|=1\)，\(k\ge3\)，把中间的一个 remove 即可。
否则存在 \(|H_i|\ge 2\)，将这个强连通分量的（被用作原图哈密尔顿回路的）哈密尔顿路径 \(P:u\to v\) 的 \(v\) remove，把它前面一个点作为路径结尾。显然这样不破坏图有哈密尔顿路，即证。
定理 2.1
对于点数 \(>6\) 的图，一次操作可以解决问题。
证明：
如果存在一个强连通分量大小大于 \(4\)：适用引理 2.1，把那个点反转，容易发现图现在强连通。
如果有超过 \(2\) 个强连通分量：反转中间的强连通分量随便一个点即可。
否则，点数 \(<6\)。
实现上，我们不需要通过刚刚的过程求出到底是哪个点，枚举然后利用性质 1.3 判断即可。
// Walawala 我是治程猴子
// Problem: Invertation in Tournament
// Platform: Luogu
// URL: https://www.luogu.com.cn/problem/CF1268D
// Memory Limit: 250 MB
// Time Limit: 3000 ms
// Author:British Union
// Long live UOB and koala
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int maxn=2005,INF=0x3f3f3f3f;
bool d[maxn][maxn];
char c[maxn];
int p[maxn],n,b[maxn];
bool check(){
for(int i=1;i<=n;i++)b[i]=p[i];
sort(b+1,b+n+1);int S=0,C=0;
for(int i=1;i<=n;i++){
S+=b[i];
if(S==i*(i-1)/2)C++;
}
return C==1;
}
int fac(int x){
if(x==0)return 1;
return x*fac(x-1);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>c+1;
for(int j=1;j<=n;j++)d[i][j]=c[j]-'0';
for(int j=1;j<=n;j++)p[i]+=d[i][j];
}
if(check()){
cout<<"0 1"<<endl;
return 0;
}
if(n>6){
int cnt=0;
for(int i=1;i<=n;i++){
p[i]=n-1-p[i];
for(int j=1;j<=n;j++){
if(i==j)continue;
if(d[i][j])p[j]++;
else p[j]--;
}
if(check())++cnt;
p[i]=n-1-p[i];
for(int j=1;j<=n;j++){
if(i==j)continue;
if(d[i][j])p[j]--;
else p[j]++;
}
}
cout<<1<<" "<<cnt<<endl;
}else{
int Min=INF,cnt=0;
for(int i=0;i<(1<<n);i++){
for(int j=1;j<=n;j++){
if(i&(1<<j-1)){
for(int k=1;k<=n;k++){
if(d[j][k])d[j][k]=0,d[k][j]=1;
else d[j][k]=1,d[k][j]=0;
}
}
}
for(int j=1;j<=n;j++){
p[j]=0;
for(int k=1;k<=n;k++)p[j]+=d[j][k];
}
if(check()){
int r=__builtin_popcount(i);
if(r<Min){
Min=r,cnt=1;
}else if(r==Min)++cnt;
}
for(int j=1;j<=n;j++){
if(i&(1<<j-1)){
for(int k=1;k<=n;k++){
if(d[j][k])d[j][k]=0,d[k][j]=1;
else d[j][k]=1,d[k][j]=0;
}
}
}
}
if(Min==INF)cout<<-1<<endl;
else cout<<Min<<" "<<cnt*fac(Min)<<endl;
}
return 0;
}