竞赛图哈密顿路径

Semsue · 2021-11-04 23:59:15 · 题解

板子题：https://www.luogu.com.cn/problem/P3561

此题题意

给你定一个竞赛图，对每个点求出一条不重复经过点的路径，使其经过的点最多。1\le n\le 2000。

竞赛图的一些性质

1，缩点之后是一条链

准确地说不是一条链，而是对于每个拓扑序在前的连通分量，都会向拓扑序再后的连通分量连边。由竞赛图的定义易知。

那么这么看这个性质就很显然了。任意两个拓扑序相邻的连通分量必有连边。

2，竞赛图必有哈密顿通路

这个可以构造证明，下文将会提到。

3，强连通竞赛图必有哈密顿回路。

这个也是构造证明，还是下文会提到。

做法

那么此题做法就很显然了，先缩点，然后对于每个强连通分量，求哈密顿回路。然后就可以对任意一个强连通分量任意点进，任意点出了。

那么重点是如何求哈密顿通路/回路。

这里给出一个 O(n^2) 的构造。记 x\to y 代表存在 x 到 y 的路径。

首先构造哈密顿通路，考虑增量构造。

假设我已经求出前 i-1 个点的一个哈密顿通路，考虑将 i 加入。设前面的哈密顿通路起点为 s 终点为 t，每个点 x 下一个点为 nxt_x。如果 t\to i 或者 i\to s 那么直接将 i 加入这条链即可，将 t 或 s 设成 i。

否则一定是下面这样：

那么显然一定存在一个 x 使得 x\to i,i\to nxt_x。将 i 插到 x,nxt_x 之间，即令 nxt_i=nxt_x,nxt_x=i 即可。

至此我们完成了哈密顿通路的构造。时间复杂度 O(n^2)。

之后考虑强连通竞赛图的哈密顿回路，首先求出哈密顿通路，还是设起点为 s，终点为 t。

考虑找到第一个 x 使得 x\to s，也就是第一可以成环的位置，设为新的 t。现在得到了一个环 s-> nxt_s-> \dots -> t-> s。这里我们不把 t-> s 这条边显示出来，也就是说 nxt_t 还是哈密顿通路上的下一个点。另外由于这个图是强连通的，所以一定可以找到这样一个 x。

然后考虑加入 nxt_t，还是设为 i。

如果 i\to s，那么直接扩展即可。否则我们直接找到第一个 x 使得 i\to x，那么我们可以简单地构造出下面这样的路径：

即设 x 的前一个是 y，那么构造 i-> x-> \dots->t-> s-> \dots-> y->i。此时为了保证 nxt_t 还是哈密顿通路上的点，我们令 s=t,t=i，修改 nxt_s 为原来的 s，nxt_y 为 i 即可。由于 x 是第一个 i\to x，所以一定有 y\to i。

如果压根找不到 x 呢？仔细想想发现确实有这种情况，因为只有后继节点有一个连向前面那么就保证了强连通的性质。既然如此，那这些点不如直接摆烂，让后面那个点去往前连，如下图：

即 i->x->\dots ->t->s->\dots->y->nxt_t->\dots->i。注意这里这里 nxt_t 即 t 在哈密顿通路中的下一个点，即图中圆圈中最左边的点。然后和上面类似，只需把 nxt_y=i 修改为 nxt_y=nxt_t，这里 t 是原来的 t。注意由于红圈中的点没有向前面连边，那么前面的每个点都会向其中的点连边，所以一定有 y\to nxt_t。

然后这样一直跑，由于强连通，所以 x 最后一定存在，所以一定会求出一条哈密顿回路其中的一条链，其中起点是 s，终点是 t 且 t\to s。

容易发现这个流程的复杂度为 O(n^2)。

好像可以做到更优复杂度，还是算了/qd。

参考代码

板子题：https://www.luogu.com.cn/problem/P3561

变量稍有不同。

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int maxn = 2005;
template <typename T>
void read(T &x) {
    T flag = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') flag = -1;
    for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    x *= flag;
}
int a[maxn][maxn];
int n, dfn[maxn], low[maxn], stk[maxn], col[maxn], top, Dfn, cnt;
bool vis[maxn];
vector<int> vec[maxn], G[maxn], V[maxn], ans[maxn];
int in[maxn];
void tarjan(int u) {
    dfn[u] = low[u] = ++Dfn;
    stk[++top] = u;
    vis[u] = 1;
    for (int v : vec[u]) {
        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]) {
        cnt++;
        while (stk[top] != u){
            col[stk[top]] = cnt;
            vis[stk[top]] = 0;
            top--;
        }
        col[u] = cnt;
        vis[u] = 0;
        top--;
    }
}
int nxt[maxn];
queue<int> q;
void solve(int c) {
    // 求强连通分量 c 的一条哈密顿回路 
    // 先求一条哈密顿通路 
    if (V[c].size() == 1)
        return;
    int s = V[c][0], t = s;
    for (int i = 1; i < (int)V[c].size(); i++) {
        int x = V[c][i];
        if (a[t][x]) nxt[t] = x, t = x;
        else if (a[x][s]) nxt[x] = s, s = x;
        else
            for (int j = s; j != t; j = nxt[j])
                if (a[j][x] && a[x][nxt[j]]) 
                    { nxt[x] = nxt[j]; nxt[j] = x; break; }
    }
    t = 0;
    for (int i = nxt[s]; i != 0; i = nxt[i]){
        if (t) {
            if (a[i][s])
                { t = i; continue; }
            for (int j = s, k = nxt[s]; j != t; j = k, k = nxt[k]) {
                if (a[i][k]) 
                    { nxt[j] = nxt[t]; nxt[t] = s; s = k; t = i; break; }
            }
        } else if (a[i][s]) t = i;
    }
    nxt[t] = s;
}
int pos[maxn];
int main() {
    read(n);
    for (int i = 2; i <= n; i++)
        for (int j = 1, x; j <= i - 1; j++){
            read(x);
            if (x)
                vec[j].eb(i), a[j][i] = 1;
            else
                vec[i].eb(j), a[i][j] = 1;
        }
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= n; i++) V[col[i]].eb(i);
    for (int i = 1; i <= n; i++)
        for (int j : vec[i])
            if (col[i] != col[j])
                G[col[i]].eb(col[j]), in[col[j]]++;
    for (int i = 1; i <= cnt; i++)
        if (!in[i]) q.push(i);
    top = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        stk[++top] = u; pos[u] = top;
        for (int v : G[u]) {
            in[v]--;
            if (!in[v]) q.push(v);
        }
    }
    for (int i = 1; i <= top; i++)
        solve(stk[i]);
    for (int i = 1; i <= n; i++) {
        int lst = i, now = pos[col[i]];
        while (1) {
            if (V[stk[now]].size() == 1) {
                ans[i].eb(lst);
                if (now == top) break;
                lst = V[stk[++now]][0];
                continue;
            }
            ans[i].eb(lst);
            for (int x = nxt[lst]; x != lst; x = nxt[x])
                ans[i].eb(x);
            if (now == top) break;
            lst = V[stk[++now]][0];
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%d ", (int)ans[i].size());
        for (int j : ans[i])
            printf("%d ", j);
        puts("");
    }
    return 0;
}

reference

https://www.cnblogs.com/TheRoadToTheGold/p/8439160.html#_label1

https://www.cnblogs.com/Hs-black/p/13749764.html

最后的最后