@bzoj - 4727@ [POI2017]Turysta

亦凉 2023-06-01 12:59 6阅读 0赞

*  @description@
 *  @solution@
    
     *  @part - 1@
     *  @part - 2@
 *  @accepted code@
 *  @details@

## @description@ ##

给出一个n个点的有向图，任意两个点之间有且仅一条有向边。  
对于每个点v，求出从v出发的一条经过点数最多，且没有重复经过同一个点两次及两次以上的简单路径。

**Input**  
第一行包含一个正整数n(2<=n<=2000)，表示点数。  
接下来n-1行，其中的第i行有i-1个数  
如果第j个数是1，那么表示有向边j->i+1，如果是0，那么表示有向边j<-i+1。

**Output**  
输出n行，第i行首先包含一个正整数k，表示从i点出发的最优路径所经过的点数  
接下来k个正整数，依次表示路径上的每个点。  
若有多组最优解，输出任意一组。

**Sample Input**  
4  
1  
1 1  
1 0 1  
**Sample Output**  
4 1 2 3 4  
3 2 3 4  
3 3 4 2  
3 4 2 3

## @solution@ ##

不难发现题目给出的是一个竞赛图。

### @part - 1@ ###

关于竞赛图，我们有以下几个性质：  
（1）竞赛图必然存在一条哈密顿路径  
（2）强连通竞赛图必然存在一条哈密顿回路  
我们可以采用归纳+构造法证明以上性质。

首先对于第一个性质，假如 n-1 个点的图存在哈密顿路径 p\[1\] -> p\[2\] -> ... -> p\[n-1\]。  
考虑加入第 n 个点 q，如果 q -> p\[1\] 或 p\[n-1\] -> q 则可以直接得到新的哈密顿路径。  
否则当 p\[1\] -> q 且 q -> p\[n-1\] 时，一定存在一个 p\[i\] 使得 p\[i\] ->q 且 q -> p\[i+1\]，将 q 塞到 p\[i\] 与 p\[i+1\] 之间即可。

然后第二个性质，考虑强连通竞赛图中，先通过上述方法构造出一个哈密顿路径 p\[1\] -> p\[2\] -> ... -> p\[n\]，然后我们沿着哈密顿路径从前往后加入点构造哈密顿回路。  
假如前 i 个点构成的强连通分量（初始情况 i = 1 即 p\[1\] 单独一个点作为强连通分量）存在哈密顿回路 q\[1...i\]，考虑加入第 i+1 个点 nw。  
此时如果回路上如果存在 j 使得 q\[j\] -> nw 且 nw -> q\[j+1\] 则可以直接把 nw 塞进去；否则，一定是回路上所有点指向 nw（因为我们是沿着哈密顿回路加入的所以不可能反过来 nw 指回去）。  
此时，在 nw 之后找到第一个点 k 使得存在一条 k->q\[j\]（因为强连通所以一定存在这个点），将 nw->...->k 这条链塞到 q\[j-1\] 与 q\[j\] 之间即可。

除此之外，竞赛图还有一个小性质：无环的竞赛图一定形成“链状”。更严谨来说，将无环竞赛图拓扑排序后，得到的拓扑序是唯一的，且拓扑序中 i 向所有 i 之后的点连边。

### @part - 2@ ###

回到题目中来，我们先将原图的强连通缩点。  
由于以上几个性质，一个点 i 出发的最长的路径一定是沿着 i 所在强连通分量的哈密顿回路绕一下 + 拓扑序中后一个分量的回路绕一下 + 。。。  
于是，路径长度等于 i 拓扑序之后的分量以及 i 所在分量大小之和，路径构造只需要构造哈密顿回路即可，构造方法参考上面的证明。

## @accepted code@ ##

#include<cstdio> #include<algorithm> using namespace std; const int MAXN = 2000; int G[MAXN + 5][MAXN + 5], n; int tid[MAXN + 5], low[MAXN + 5], dcnt = 0; int num[MAXN + 5], siz[MAXN + 5], tot = 0; int vis[MAXN + 5], stk[MAXN + 5], tp = 0; void dfs(int x) { tid[x] = low[x] = (++dcnt); stk[++tp] = x, vis[x] = true; for(int i=1;i<=n;i++) { if( !G[x][i] ) continue; if( !tid[i] ) dfs(i), low[x] = min(low[x], low[i]); else if( vis[i] ) low[x] = min(low[x], tid[i]); } if( low[x] >= tid[x] ) { tot++; while( tp && tid[stk[tp]] >= tid[x] ) { num[stk[tp]] = tot, vis[stk[tp]] = false; siz[tot]++, tp--; } } } int G2[MAXN + 5][MAXN + 5], deg[MAXN + 5], id[MAXN + 5]; int hd[MAXN + 5], tl[MAXN + 5], nw[MAXN + 5]; int ans[MAXN + 5], nxt[MAXN + 5]; int read() { int x = 0; char ch = getchar(); while( ch < '0' || ch > '9' ) ch = getchar(); while( '0' <= ch && ch <= '9' ) x = 10*x + ch - '0', ch = getchar(); return x; } void write(int x) { if( !x ) return ; write(x/10); putchar(x%10 + '0'); } void print(int x) { int p = x; do { putchar(' '), write(p); p = nxt[p]; }while( p != x ); if( deg[num[x]] ) print(hd[id[deg[num[x]] - 1]]); } int main() { n = read(); for(int i=2;i<=n;i++) { for(int j=1;j<i;j++) { int x = read(); G[j][i] = x, G[i][j] = (!x); } } for(int i=1;i<=n;i++) if( !tid[i] ) dfs(i); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if( G[i][j] && num[i] != num[j] ) G2[num[i]][num[j]] = true; for(int i=1;i<=tot;i++) { ans[i] = siz[i]; for(int j=1;j<=tot;j++) if( G2[i][j] ) deg[i]++, ans[i] += siz[j]; id[deg[i]] = i; hd[i] = tl[i] = 0; } for(int i=1;i<=n;i++) { nxt[i] = -1; if( !hd[num[i]] ) hd[num[i]] = tl[num[i]] = i; else { if( G[i][hd[num[i]]] ) nxt[i] = hd[num[i]], hd[num[i]] = i; else if( G[tl[num[i]]][i] ) nxt[tl[num[i]]] = i, tl[num[i]] = i; else { int p = hd[num[i]]; while( nxt[p] != -1 ) { if( G[p][i] && G[i][nxt[p]] ) { nxt[i] = nxt[p], nxt[p] = i; break; } p = nxt[p]; } } } } for(int i=1;i<=tot;i++) { int p = nxt[hd[i]]; nw[i] = 0, nxt[hd[i]] = hd[i]; while( p != -1 ) { if( nw[i] ) { int r = hd[i]; do { if( G[p][nxt[r]] ) { int q = nxt[p]; nxt[p] = nxt[r], nxt[r] = nw[i], p = q; nw[i] = 0; break; } r = nxt[r]; }while( r != hd[i] ); if( nw[i] ) p = nxt[p]; } else { int r = hd[i]; bool flag = false; do { if( G[r][p] && G[p][nxt[r]] ) { int q = nxt[p]; nxt[p] = nxt[r], nxt[r] = p, p = q; flag = true; break; } r = nxt[r]; }while( r != hd[i] ); if( !flag ) nw[i] = p, p = nxt[p]; } } } for(int i=1;i<=n;i++) { write(ans[num[i]]); print(i), puts(""); } }

## @details@ ##

一开始凭着感觉并没有利用哈密顿路径构造哈密顿回路然后 WA 了好几次。

后来又开始 TLE，调了一会儿发现我某个地方没有写 p = nxt\[p\]。。。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11381034.html