Skip to content

S2OJ - 1506. Antifloyd

题解约 1 千字
# S2OJ # 图论 # Tarjan # Floyd
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

传说中有一种神奇的算法叫做 Floyd，它竟然能算出一张有向图的传递闭包（一张记录了每个点对之间是否连通的表）！

但是现在出现了一个难题，国王想要建立一个特殊的省供 OIer 生活，省内包含许多城市，国王得到一份「传递闭包」，就是一个 N×NN \times N 的 0101 矩阵，第 ii 行第 jj 列表示城市 ii 到城市 jj 之间是否有单向需求通讯（00 是不需求，11 是需求）。如果城市 AA 想与城市 BB 之间通讯，则需要建立一条光缆（由于国王手下的废材工程员，光缆竟然是单向的，如果有一条光缆从 AA 到 BB，则 AA 可以发讯息到 BB，但是 BB 不能发讯息到 AA）。光缆是具有连续性的，比如说 AA 有条光缆到 BB，BB 有条光缆到 CC，则 AA 可以发送讯息到 CC，所以国王拿到的那份「传递闭包」中，不可能出现 A→BA \to B，B→CB \to C 但是 AA 不能到 CC 这种情况。

由于经费问题，所以国王想要用最少的光缆完成城市信息网的建立，然而手下的那群好吃懒做的程序员啊，国王很头疼，所以请到了传说中的哥，要求解决这个问题。

#输入格式

第一行一个整数 NN。之后的 NN 行每行 NN 个为 00 或 11 的整数，表示题中所述的 0101 矩阵。

#输出格式

一行一个整数，表示最少需要多少条光缆。

#输入输出样例

样例输入 #1

3
1 1 1
1 1 1
1 1 1

样例输出 #1

3

#数据规模与约定

对于 20%20\% 的数据，1≤N≤51 \leq N \leq 5；
对于 100%100\% 的数据，1≤N≤2001 \leq N \leq 200。

#思路

首先，本题的图中存在两种结构：链和环。一个有 NN 个点链需要消耗 N−1N - 1 条光缆，一个有 NN 个点环需要消耗 NN 条光缆。环可以跑一遍 Tarjan 缩成一个点方便后续处理。

然后可以发现，当存在 A→BA \to B 和 B→CB \to C 的光缆时，如果再出现 A→CA \to C 的通信需求就不需要再新建光缆了，直接复用 A→B→CA \to B \to C 的链路即可。于是可以想到在缩完点后的新图上跑一边「反向」的 Floyd，将这种可以通过复用链路的边删掉。

最后统计答案即可。

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <stack>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 205;

int n, ans;
bool g[N][N], g2[N][N];

// Tarjan
int cnt, dfn[N], low[N];
int scc_cnt, id[N], siz[N];
int dout[N], din[N];
bool vis[N];
std::stack<int> st;

void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    st.push(u);
    vis[u] = true;

    for (int i = 1; i <= n; i++) {
        if (!g[u][i]) continue;

        if (!dfn[i]) {
            tarjan(i);
            low[u] = std::min(low[u], low[i]);
        } else if (vis[i]) {
            low[u] = std::min(low[u], dfn[i]);
        }
    }

    if (dfn[u] == low[u]) {
        scc_cnt++;

        int v;
        do {
            v = st.top();
            st.pop();
            vis[v] = false;
            id[v] = scc_cnt;
            siz[scc_cnt]++;
        } while (v != u);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> g[i][j];
        }
    }

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (g[i][j] && id[i] != id[j]) {
                g2[id[i]][id[j]] = true;
            }
        }
    }

    for (int i = 1; i <= scc_cnt; i++) {
        for (int j = 1; j <= scc_cnt; j++) {
            for (int k = 1; k <= scc_cnt; k++) {
                if (i != j && j != k && g2[i][k] && g2[k][j]) {
                    g2[i][j] = false;
                }
            }
        }
    }

    for (int i = 1; i <= scc_cnt; i++) {
        if (siz[i] > 1) ans += siz[scc_cnt];

        for (int j = 1; j <= scc_cnt; j++) {
            if (g2[i][j]) ans++;
        }
    }

    cout << ans << endl;

    return 0;
}