Description

题目链接:Codeforces 1138E

在国家 $N$ 中,有 $n$ 个城市通过 $m$ 条单向道路连接。尽管这个国家看起来并不是那么引人注目,但是这里有两件很有意思的事情。首先,这里的一周有 $d$ 天;另外,每个城市恰好有一个博物馆。

旅行社的员工知道每个博物馆的开放日期,他们正在为游客们制定一项新的旅游计划。旅游从标号为 $1$ 的首都城市出发,并且旅游的第一天必须在某一周的第一天。每天白天,如果当前城市的博物馆开放,那么游客可以进入博物馆参观;否则什么都做不了。晚上,游客要么结束旅游,要么通过道路前往下一个城市。注意,旅游过程中允许重复经过同一个城市。

你需要为旅游制定一条路线,使得在旅游期间参观的不同博物馆数量最多。

数据范围:$1 \le n \le 10 ^ 5$,$0 \le m \le 10 ^ 5$,$1 \le d \le 50$。


Solution

首先把每个点 $u$ 拆成 $d$ 个点 $u_0, u_1, \dots, u_{d - 1}$,这样一条边 $(u, v)$ 转化为 $(u_0, v_1), (u_1, v_2), \dots, (u_{d - 1}, v_0)$ 这 $d$ 条边。由于同一个强连通分量内的点是相互可达的,那么我们把这张图缩成一个 $\text{DAG}$,然后进行 $\text{DP}$ 计数。

但是我代码写到一半突然发现一个问题:如果有两个点 $u_i, u_j(i \ne j)$ 存在于不同的强连通分量中,且这两个强连通分量可达(拓扑排序或 $\text{DFS}$ 时会重复计数),怎么才能不重复计数?难道需要 $\text{set}$ 去重?启发式合并?并且支持撤回操作?

接下来我们就证明如下结论:如果从点 $u_i$ 可以到达 $u_j(i \ne j)$,那么这两个点一定在同一个强连通分量中。设 $\Delta = j - i$,那么一定存在这样一条路径:$u_i \rightarrow u_j \rightarrow u_{j + \Delta} \rightarrow u_{j + 2\Delta} \rightarrow \dots \rightarrow u_{j + (d - 1)\Delta}$(此处的下标均对 $d$ 取模),发现 $j + (d - 1)\Delta = i \pmod d$,因此一定可以从 $u_j$ 回到 $u_i$。这意味着 $u_i, u_j$ 一定在同一个强连通分量中。

证明了这个结论后,可以直接 $\text{tarjan}$ 缩点后 $\text{DP}$ 了。

时间复杂度:$\mathcal O((n + m) \cdot d)$。


Code

#include <cstdio>
#include <algorithm>

const int N = 5e6 + 5;

int n, m, d, tag[N], sz[N], f[N];
int cnt, idx, top, stk[N], dfn[N], low[N], scc[N];
bool vis[N];
char s[100005][51];

template <int N, int M>
struct Graph {
    int tot, lnk[N], ter[M], nxt[M];
    void add(int u, int v) {
        ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
    }
};

Graph<N, N> G1, G2;

int id(int x, int t) {
    return (x - 1) * d + t + 1;
}
void tarjan(Graph<N, N> &G, int u) {
    dfn[u] = low[u] = ++idx;
    stk[++top] = u, vis[u] = true;
    for (int i = G.lnk[u]; i; i = G.nxt[i]) {
        int v = G.ter[i];
        if (!dfn[v]) {
            tarjan(G, v);
            low[u] = std::min(low[u], low[v]);
        } else {
            if (vis[v]) low[u] = std::min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        ++cnt;
        do {
            u = stk[top--], scc[u] = cnt, vis[u] = false;
        } while (dfn[u] != low[u]);
    }
}
int dfs(Graph<N, N> &G, int u) {
    if (f[u]) return f[u];
    for (int i = G.lnk[u]; i; i = G.nxt[i]) {
        f[u] = std::max(f[u], dfs(G, G.ter[i]));
    }
    return f[u] += sz[u];
}
int main() {
    scanf("%d%d%d", &n, &m, &d);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        for (int j = 0; j < d; j++) {
            G1.add(id(u, j), id(v, (j + 1) % d));
        }
    }
    for (int i = 1; i <= n; i++) scanf("%s", s[i]);
    tarjan(G1, 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < d; j++) {
            int u = id(i, j);
            if (s[i][j] == '1' && tag[scc[u]] != i) {
                tag[scc[u]] = i, sz[scc[u]]++;
            }
            for (int i = G1.lnk[u]; i; i = G1.nxt[i]) {
                int v = G1.ter[i];
                if (scc[u] != scc[v]) G2.add(scc[u], scc[v]);
            }
        }
    }
    printf("%d\n", dfs(G2, scc[1]));
    return 0;
}

标签: Codeforces, 图论, 动态规划, 缩点, Tarjan

添加新评论

请填写正确的称呼和 Email,否则评论将被删除。