P3561 Turysta
灰常诡异的图论
P3561
题意：
一\(n\)个点的有向图，保证任意两个点间有且仅有一条边，对于每个点\(u\)，求出一条从\(u\)出发的经过点最多的路径（点不能重复走）。
题解
先说明几个概念：
- 竞赛图：一个有向图，每对顶点之间都有一条边。
- 哈密顿通路：在一个有向图或无向图中经过每个节点一次且仅一次的通路称作哈密顿通路。
- 哈密顿回路：图G的一个回路，若它只通过图的每一个节点一次，就是哈密顿回路。
- 哈密顿图：能找到一条路径，从一点出发，必须经过所有的点一次,最终回到起点的图。（图中有的边可以不经过,但是不会有边被经过两次）。
还有几个性质：
- 设\(G\)是有\(n\)个点的无向简单图，若对于\(G\)中任意不相邻的顶点\(v_i\)，\(v_j\)，均有\(d(v_i)+d(v_j)\geqslant n-1\)，则G中存在哈密顿通路。（这个没有大用，至少和这道题一点关系都木有）
- 设\(G\)是有\(n\)个点的无向简单图，若对于\(G\)中任意不相邻的顶点\(v_i\)，\(v_j\)，均有\(d(v_i)+d(v_j)\geqslant n\)，则G中存在哈密顿回路。（还是木有用）
- 有割点的图一定不是哈密顿图。（同样木有用）
- 竞赛图一定存在哈密顿通路。
- 强连通竞赛图一定存在哈密顿回路。
现在描述如何通过竞赛图构造哈密顿通路。
假设现在已经有一条路径\(v_1\to v_2\to v_3\to v_4\)。如果下一个点\(v_5\)直接和路径起点\((s)\ \ v_1\)连边，路径起点换到\(v_5\)，整个路径变为\(v_5\to v_1\to v_2\to v_3\to v_4\)（恭喜我们的路径延长啦）。如果\(v_5\)和路径尾部\((t)\)直接连边同理。其余情况一定有中间某一个点（设为\(v_x\)）向\(v_5\)连边，\(v_5\)再向\(v_x\)在原路径上的下一个点连边（把这句话简单证明一下：在竞赛图中\(v_5\)会和所有的点有边相连，假设是路径上其他点向\(v_5\)连边为状态\(0\)，\(v_5\)向路径上其他点连边为状态\(0\)，如果路径上相邻两点状态不同\(v_5\)就可以插入其中，此时路径首尾点和\(v_5\)的状态一定不同（此时为\(s\)指向\(v_5\)，\(v_5\)指向\(t\)）），这样就可以把\(v_5\)插入到\(v_x\)后面（恭喜我们的路径有扩张啦）。
现在已经有哈密顿通路（起点为\(s\)，终点为\(t\)）啦，考虑在强连通竞赛图中构造哈密顿回路。
先在路径上找到一个指向\(s\)的点\(x_1\)（第一个可以成环），把\(x_1\)变成新的\(t\)，现在有了的一个环。设点\(x_1\)的下一个点为\(i\)，如果\(i\)直接指向\(s\)，就直接扩展，要不然可以顺着从\(s\)到\(t\)（现在的\(t\)是找到第一个环后新的\(t\)）找到第一个\(x_2\)满足\(i\to x_2\)，设\(x_2\)在路径上前面一个点为\(y\)，现在构造出了一条\(i\to x_2\to ... \to t\to s\to... \to y\to i\)的路径，现在让刚刚得\(t\)成为新的\(s\)，刚刚的\(i\)成为新的\(t\)。如果找不到\(x_2\)满足\(i\to x_2\)就跳过这个\(i\)顺着路径找到下一个点使它成为新的\(i\)。
现在我们已经有了每一个强连通分量中的哈密顿回路，可以做到任意进出每一个强连通分量，对所有的强连通分量拓扑排序，然后对每个点求答案，先按照所在强连通分量的哈密顿回路取每个点，然后在跳到拓扑序在这个强连通分量后面的强连通分量中继续取哈密顿回路上的点，最后输出答案即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn=2e3+10;
int scc[maxn],dfn[maxn],low[maxn],vis[maxn],s[maxn],tp,dfn1,scc1;
vector<int> v[maxn];
int to[maxn][maxn],nxt[maxn];
vector<int> ans[maxn];
void tarjan(int u)
{
dfn[u]=low[u]=++dfn1; s[++tp]=u; vis[u]=1;
for(int v=1;v<=n;v++)
{
if(to[u][v])
{
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u])
{
scc1++;
while(s[tp]!=u)
{
v[scc1].push_back(s[tp]); scc[s[tp]]=scc1; vis[s[tp]]=0; tp--;
}
v[scc1].push_back(u); scc[u]=scc1; vis[u]=0; tp--;
}
}
void solve(int a)
{
if(v[a].size()==1) return;
int s,t,x;
s=t=v[a][0];
for(int i=1;i<v[a].size();i++)
{
x=v[a][i];
if(to[t][x]){nxt[t]=x;t=x;continue;}
if(to[x][s]){nxt[x]=s;s=x;continue;}
for(int j=s;j!=t;j=nxt[j])
{
if(to[j][x]&&to[x][nxt[j]])
{
nxt[x]=nxt[j];
nxt[j]=x;
break;
}
}
}
t=0;
for(int i=nxt[s];i;i=nxt[i])
{
if(to[i][s]) t=i;
else if(t!=0)
{
for(int j=s;j!=t;j=nxt[j])
{
if(to[i][nxt[j]])
{
x=nxt[j];nxt[j]=nxt[t];nxt[t]=s;s=x;t=i;break;
}
}
}
}
nxt[t]=s;
}
int main()
{
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
for(int j=1;j<=i-1;j++)
{
int x; scanf("%d",&x);
if(x==1) to[j][i]=1;
else to[i][j]=1;
}
}
for(int i=1;i<=n;i++)
{
if(!dfn[i]) tarjan(i);
}
for(int i=1;i<=scc1;i++)
{
solve(i);
}
int x,k;
for(int i=1;i<=n;i++)
{
x=i;k=scc[i];
while(1)
{
ans[i].push_back(x);
if(v[k].size()==1)
{
if(k==1) break;
k--;
x=v[k][0]; continue;
}
for(int j=nxt[x];j!=x;j=nxt[j])
{
ans[i].push_back(j);
}
if(k==1) break;
k--; x=v[k][0];
}
}
for(int i=1;i<=n;i++)
{
cout<<ans[i].size()<<' ';
for(int j=0;j<ans[i].size();j++)
{
printf("%d ",ans[i][j]);
}
printf("\n");
}
}
写在后面
希望遇到知道哈密顿图的简单充要条件的友友来分享。
标签：连通,哈密顿,int,路径,POI2017,maxn,回路 From： https://www.cnblogs.com/PHOTONwa/p/17727248.html