BZOJ 3887 - [Usaco2015 Jan]Grass Cownoisseur

#DP #tarjan #枚举
Published on 2016-06-23

题目地址

描述

给一个含有 n(n≤100000)n(n\le 100000) 个点有向图，然后选一条路径起点终点都为 11 的路径出来，有一次机会可以沿某条边逆方向走，问最多有多少个点可以被经过？（一个点在路径中无论出现多少正整数次对答案的贡献均为 11）

分析

对于这种有限制/有特殊条件的题，一定要想着怎么从无限制的情况转化。

那么对于这个题，圈，显然可以全部走过，进行 tarjan 缩点。
如果没有限制，那么答案就是 11 所在强连通分量的大小。现在有一次反向某条边的机会，怎么利用这次机会呢？当然是要形成一个包含 11 所在的圈，答案才有可能增大，如果反向后的边是 u→vu \rightarrow v，那么这个圈一定是 1→u→v→11 \rightarrow u \rightarrow v \rightarrow 1，如果能知道 11 到 uu 和 vv 到 11 的最长路（这两条路径不可能有重复的点，否则就有环了），就可枚举每条边，在 O(1)O(1) 的时间内求出反向这条边的答案了。

缩点后正向做一次拓扑排序，可以求得 11 到所有点的最长路（技巧是先初始化到每个点的最长路为 −∞-\infty，当处理到 11 的时候，再将到 11 的最长路设置为 00）。同理，反向做一次拓扑排序，可以求得所有点到 11 的最长路。

P.S. 最长路是一条最长的路径，使得路径上的点的强联通分量大小和最大。

代码

//  Created by Sengxian on 6/23/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3887 tarjan
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 100000 + 3;
vector<int> G[maxn], nG[maxn], rG[maxn];
int n, m, dfn[maxn], sccno[maxn], scc_sz[maxn], timestamp = 0, scc_cnt = 0;
int in[maxn * 2];

stack<int> stk;
int dfs(int u) {
    int low = dfn[u] = ++timestamp;
    stk.push(u);
    for (int i = 0; i < (int)G[u].size(); ++i) {
        int v = G[u][i];
        if (!dfn[v]) low = min(low, dfs(v));
        else if (sccno[v] == -1) low = min(low, dfn[v]);
    }
    if (low == dfn[u]) {
        do {
            int v = stk.top(); stk.pop();
            scc_sz[scc_cnt]++;
            sccno[v] = scc_cnt;
            if (u == v) break;
        } while (!stk.empty());
        scc_cnt++;
    }
    return low;
}

int f1[maxn], f2[maxn];
void solve(int n, vector<int> G[maxn], int dp[maxn]) {
    queue<int> q;
    memset(dp, -0x3f, sizeof (int) * n);
    memset(in, 0, sizeof in);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < (int)G[i].size(); ++j)
            in[G[i][j]]++;
    for (int i = 0; i < scc_cnt; ++i)
        if (!in[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == sccno[0]) dp[u] = 0;
        dp[u] += scc_sz[u];
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            dp[v] = max(dp[v], dp[u]);
            if (--in[v] == 0) q.push(v);
        }
    }
}


char str[maxn];
int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), m = ReadInt();
    for (int i = 0; i < m; ++i) {
        int f = ReadInt() - 1, t = ReadInt() - 1;
        G[f].push_back(t);
    }
    timestamp = 0, scc_cnt = 0;
    memset(sccno, -1, sizeof sccno);
    for (int i = 0; i < n; ++i) if (!dfn[i]) dfs(i);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < (int)G[i].size(); ++j) {
            int v = G[i][j];
            if (sccno[i] != sccno[v]) nG[sccno[i]].push_back(sccno[v]), rG[sccno[v]].push_back(sccno[i]);
        }
    }
    solve(scc_cnt, nG, f1), solve(scc_cnt, rG, f2);
    int ans = scc_sz[sccno[0]];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < (int)G[i].size(); ++j) {
            int v = G[i][j];
            if (sccno[i] != sccno[v]) ans = max(ans, f1[sccno[v]] + f2[sccno[i]] - scc_sz[sccno[0]]);
        }
    }
    printf("%d\n", ans);
    return 0;
}
Codeforces 685B - Kay and Snowflake