在纪中集训课件里面看见的这句话qwq,当时没会于是考试就遭报应了qwq赶紧学一学..
定义:
有向完全图称为竞赛图。
不重不漏地经过图上所有点的简单路径叫做哈密顿通路。
最后回到起点的哈密顿通路叫做哈密顿回路。
一些结论:
竞赛图一定有哈密顿通路。
强连通竞赛图一定有哈密顿回路。
这两条结论都可以用数学归纳法证明,而且可以基于数学归纳的思路给出的构造。
第一条结论比较简单,我们直接上代码注释就好了。
l=r=1;//我们一个个往里插点,维护l到r用nxt连起来的一条路径。
for(int i=2;i<=n;p++){
if(a[i][l])nxt[i]=l,l=i;
else if(a[r][i])nxt[r]=i,r=i;//这两个情况十分显然。
else{
for(int j=l;;j=nxt[j])
if(a[j][i]&&a[i][nxt[j]]){//此时我们已知l->i,i->r,则在链中一定会有一个点满足此条件。在此插入即可
nxt[i]=nxt[j],nxt[j]=i;
break;
}
}
}
对于强连通的竞赛图,我们想要构造出它的一条哈密顿回路。首先我们求出一条哈密顿通路l->r。然后在l->r这条链上遍历找到第一个到l有连边的点p(一定会找到,否则不强连通...)。此时我们已经有了一个环,考虑对后面的点都插入环。具体见代码吧233
//这个部分最好画图理解,图是一个环长一条尾巴的样子。
r=0;//这里是紧接着上面找完通路。先把r置为0表示还没有找到初始的环。
for(int i=l;i;i=nxt[i])//r是环上最靠近链的点,r->l是环上的边,r->nxt[r]是链上的边。
if(r){//尝试在环中插入点i
for(int j=l,k=r;;k=j,j=nxt[j]){
if(a[i][j]){//在环上找到一个可以作为nxt[i]的点。
nxt[k]=nxt[r];//j作为了i的后继,那么本来j的前驱k就要另找一个后继了。（这里注意nxt[r]不一定是i，因为可能前面的一些点没有插入成功）
if(k!=r)nxt[r]=l;//本来没有连上的环上的边要连上(k=r的话r的后继在上一句话已经改了,不是l了)
l=j,r=i;break;//根据l和r的定义修改l和r
}
if(j==r)break;//确实有可能当前无法插入，但是后面的点一定会有插入成功的，那时这个点也就会进入环内。
}
}
else if(a[i][l])r=i;//这里找到了初始的环
nxt[r]=l;//这里把最后一条边连上。
这个东西可能现推真的很困难吧...细节这么多...又这么巧妙...
我的注释真的有够清楚了qwq肯定能看懂的qwq
这两条性质对于竞赛图上的问题非常有帮助
竞赛图上最长路问题BZOJ4727:对于竞赛图上每个点i求出一条从i出发的最长简单路径。
解决这个问题还有一个比较显然的结论:
竞赛图对强连通分量缩点后是一条链。
证明的话考虑竞赛图两两点之间都有关系,于是拓扑序只有一种(比较感性,其实也可以数学归纳)
这个先缩点,那么对于一个强连通分量里的点都能到达,分量之间的点又是两两都有边,那么显然可以得到就是从点i所在分量走完缩完后的链,分量中走一个哈密顿回路即可。
注：求一个哈密顿回路也可以随机好多次哈密顿路径，然后判断首尾是否相连。