跳转至

学校网络

原题链接

题目描述

一些学校连接在一个计算机网络上，学校之间存在软件支援协议，每个学校都有它应支援的学校名单（学校 A 支援学校 B，并不表示学校 B 一定要支援学校 A）。

当某校获得一个新软件时，无论是直接获得还是通过网络获得，该校都应立即将这个软件通过网络传送给它应支援的学校。

因此，一个新软件若想让所有学校都能使用，只需将其提供给一些学校即可。

现在请问最少需要将一个新软件直接提供给多少个学校，才能使软件能够通过网络被传送到所有学校？

最少需要添加几条新的支援关系，使得将一个新软件提供给任何一个学校，其他所有学校就都可以通过网络获得该软件？

强连通分量

分析

\(Tarjan\) 缩点将原图转化成 \(DAG\)，统计每个强连通分量的出度入度，起点数量为 \(src\)，终点数量为 \(des\)。对于一个强连通分量，其中只要有一所学校获得新软件那么整个分量都能获得。

问题一

结论

只要把软件给所有起点即可，答案为起点个数 \(src\)。

证明

所有起点都无法由别的点到达，因此每个起点必须分配一个软件，而对于其他所有点，一定存在前驱，一定能由某一个起点走到，也就是说从所有起点出发，能遍历整个图。因此只需要给所有起点各一个软件即可。

问题二

结论
  1. 若 \(scc\_{cnt}=1\)（只有一个强连通分量），则不需要连新的边，答案为 \(0\)。
  2. 若 \(scc\_{cnt}>1\)，则答案为 \(\max(src,des)\)。
证明

结论 \(1\) 正确性显然，下面证明结论 \(2\)。

设缩点后的 \(DAG\) 中，起点（入度为 \(0\)）的集合为 \(P\)，终点（出度为 \(0\)）的集合为 \(Q\)。分以下两种情况讨论：

  • \(|P|≤|Q|\)

    1. 若 \(|P|=1\)，则只有一个起点，并且这个起点能走到所有点，只要将每一个终点都向这个起点连一条边，那么对于图中任意一点，都可以到达所有点，新加的边数为 \(|Q|\)。

    2. 若 \(|P|≥2\)，则 \(|Q|≥|P|≥2\)，此时至少存在 \(2\) 个起点 \(p_1,p_2\)，2 个终点 \(q_1,q_2\)，满足 \(p_1\) 能走到 \(q_1\)，\(p_2\) 能走到 \(q_2\)。（反证法：如果不存在两个起点能走到不同的终点，则所有的起点一定只能走到同一个终点，而终点至少有两个，发生矛盾，假设不成立）。如下图：

    那么我们可以从 \(q_1\) 向 \(p_2\) 新连一条边，那么此时起点和终点的个数都会减少一个（\(p_2\) 不再是起点，\(q_1\) 不再是终点），因此只要以这种方式，连接新边 \(|P|−1\) 条，则 \(|P′|=1\)，而 \(|Q′|=|Q|−(|P|−1)\)，由 ① 得，当 \(|P′|=1\) 时，需要再连 \(|Q′|\) 条新边，那么总添加的新边数量为 \(|P|−1+|Q|−(|P|−1)=|Q|\)。

  • \(|Q|≤|P|\)

    与情况 \(1\) 对称，此时答案为 \(|P|\)。

综上所述，\(scc\_cnt>1\) 时，问题二的答案为 \(max(|P|,|Q|)\) 即 \(max(src,des)\) 。

代码

 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
#include <bits/stdc++.h>
using namespace std;

const int N = 110 , M = N * N;

int n;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], scc[N], dfncnt, sc;
bool stk[N];
int din[N], dout[N];
stack<int> S;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++dfncnt;
    S.push(u);
    stk[u] = true;

    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u]) {
        int y;
        sc++;
        do {
            y = S.top();
            S.pop();
            stk[y] = false;
            scc[y] = sc;
        } while (y != u);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        while (cin >> x, x) {
            add(i, x);
        }
    }

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

    for (int i = 1; i <= n; i++)
        for (int j = h[i]; j != -1; j = ne[j]) {
            int k = e[j];
            int a = scc[i], b = scc[k];
            if (a != b) {
                din[b]++;
                dout[a]++;
            }
        }

    int a = 0, b = 0;
    for (int i = 1; i <= sc; i++) {
        if (!din[i]) a++;
        if (!dout[i]) b++;
    }

    cout << a << endl;
    if (sc == 1) cout << 0 << endl;
    else cout << max(a, b) << endl;

    return 0;
}
回到页面顶部