【E6.0.13】强连通分量笔记，但是极速版

· · 题解

受欢迎的牛

若一个强连通的出度为 0，则该强连通分量中的所有点都被其他强连通分量的牛欢迎。

但假如存在两及以上个出度为 0 的牛(强连通分量)，则答案为 0。

for (int i = 1; i <= n; i ++ )
    if (!dfn[i]) tarjan(i);

for (int u = 1; u <= n; u ++ )
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i], a = id[u], b = id[j];
        if (a != b) d[a] ++ ;
    }

int res = 0, sum = 0;
for (int i = 1; i <= scc_cnt; i ++ )
    if (!d[i])
    {
        res ++ ;
        sum += sz[i];
        if (res > 1)
        {
            sum = 0;
            break;
        }
    }

最大半连通子图

Tarjan 缩点之后跑 DP。

注意取重边算作相同方案。 ```cpp for (int i = 1; i <= n; i ++ ) if (!dfn[i]) tarjan(i); unordered_set<int> S; for (int u = 1; u <= n; u ++ ) for (int i = h[u]; ~i; i = ne[i]) { int j = e[i], a = id[u], b = id[j]; int hsh = a * (int)1e6 + b; if (a != b && !S.count(hsh)) { S.insert(hsh); add(hh, a, b); } } for (int u = scc_cnt; u; u -- ) { if (!f[u]) f[u] = sz[u], g[u] = 1; for (int i = hh[u]; ~i; i = ne[i]) { int j = e[i]; if (f[j] < f[u] + sz[j]) { f[j] = f[u] + sz[j]; g[j] = g[u]; } else if (f[j] == f[u] + sz[j]) g[j] = (g[j] + g[u]) % mod; } } int r1 = 0, r2 = 0; for (int i = 1; i <= scc_cnt; i ++ ) if (f[i] > r1) r1 = f[i], r2 = g[i]; else if (f[i] == r1) r2 = (r2 + g[i]) % mod; ``` ### 学校网络 考虑缩点后 DAG 的性质，只支持单向传送。 设该 DAG 有 $x$ 个起点（入度为零），$y$ 个终点（出度为零）。 于是第一问直接输出 $x$ 即可。 第二问考虑将所有头 -> 尾的链首尾相连，那么答案为 $\max(x,y)$。 ```cpp for (int i = 1; i <= n; i ++ ) if (!dfn[i]) tarjan(i); for (int u = 1; u <= n; u ++ ) for (int i = h[u]; ~i; i = ne[i]) { int j = e[i], a = id[u], b = id[j]; if (a != b) din[b] ++ , dout[a] ++ ; } int r1 = 0, r2 = 0; for (int i = 1; i <= scc_cnt; i ++ ) { if (!din[i]) r1 ++ ; if (!dout[i]) r2 ++ ; } if (scc_cnt == 1 && r1 == 1 && r2 == 1) puts("1\n0"); else printf("%d\n%d\n", r1, max(r1, r2)); ``` ### 消息的传递 和上题一样，输出起点个数即可。 ```cpp for (int i = 1; i <= n; i ++ ) if (!dfn[i]) tarjan(i); for (int u = 1; u <= n; u ++ ) for (int i = 1; i <= n; i ++ ) if (g[u][i]) { int a = id[u], b = id[i]; if (a != b) din[b] ++ ; } int cnt = 0; for (int i = 1; i <= scc_cnt; i ++ ) if (!din[i]) cnt ++ ; ``` ### 间谍网络 还是这道题😅。唯一不同的是需要维护 scc 中权值和。 ```cpp for (int i = 1; i <= n; i ++ ) if (!dfn[i] && w[i] != INF) tarjan(i); for (int i = 1; i <= n; i ++ ) if (!dfn[i]) return printf("NO\n%d\n", i) & 0; for (int u = 1; u <= n; u ++ ) for (int i = h[u]; ~i; i = ne[i]) { int j = e[i], a = id[u], b = id[j]; if (a != b) din[b] ++ ; } int res = 0; for (int i = 1; i <= scc_cnt; i ++ ) if (!din[i]) res += nw[i]; ``` ### 搬运计划 缩点之后跑关于点权的 Dijkstra，然后枚举所有酒吧的值取 $\max$ 即可。 ```cpp for (int i = 1; i <= n; i ++ ) if (!dfn[i]) tarjan(i); for (int u = 1; u <= n; u ++ ) for (int i = h[u]; ~i; i = ne[i]) { int j = e[i], a = id[u], b = id[j]; if (a != b) add(nh, a, b); } dijkstra(id[S]); int res = p[1]; for (int i = 1; i <= T; i ++ ) if (dist[id[res]] < dist[id[p[i]]]) res = p[i]; ``` ### 和平委员会 2-SAT 板子，但是 CSP 不考。 ```cpp int get(int x) { if (x & 1) x ++ ; else x -- ; return x; } signed main() { int a, b; memset(h, -1, sizeof h); scanf("%lld%lld", &n, &m); while (m -- ) { scanf("%lld%lld", &a, &b); add(a, get(b)), add(b, get(a)); } for (int i = 1; i <= n << 1; i ++ ) if (!dfn[i]) tarjan(i); for (int i = 1; i <= 2 * n; i += 2) if (id[i] == id[i + 1]) return puts("NO"), 0; puts("YES"); return 0; } ```