题面：[USACO5.3] Network of Schools
大秦为你打开题目传送门
题目描述
一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 $B$ 在 $A$ 学校的分发列表中，$A$ 也不一定在 $B$ 学校的列表中。
你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。
输入格式
输入文件的第一行包括一个正整数 $N$，表示网络中的学校数目。学校用前 $N$ 个正整数标识。
接下来 $N$ 行中每行都表示一个接收学校列表（分发列表），第 $i+1$ 行包括学校 $i$ 的接收学校的标识符。每个列表用 $0$ 结束，空列表只用一个 $0$ 表示。
输出格式
你的程序应该在输出文件中输出两行。
第一行应该包括一个正整数，表示子任务 A 的解。
第二行应该包括一个非负整数，表示子任务 B 的解。
样例 #1
样例输入 #1
样例输出 #1
提示
$2 \le N \le 100$。
题目翻译来自NOCOW。
USACO Training Section 5.3
思路
把题目的两个任务拎出来：
- 为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目
- 计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校
概括成图论的话，第一个任务好说，就是求入度为 0 的点；但是如果是任务二，我们就是要把一个 DAG 变成 SCC ，怎么办？不难发现，所谓环就是所有点都有入度和出度，也就是说，我们只需要把出度为 0 的点连接到入度为 0 的点。每次连接一条边，我们一定会减少一个入度为 0 一个出度为 0 的点，那么其实方案数就是入度为 0 或者或者出度为 0 的点的数量较大值。
代码
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int > pii;
typedef unsigned long long ull;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
const int MaxV = 1e5 + 10;
const int MaxE = 5e5 + 10;
template<int N, int M>
class Graph {
private :
struct Edge {
int to, nt, wt;
Edge() {}
Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
}e[M];
int hd[N], cnte;
public :
inline void clear() { memset(hd, 0, sizeof(hd)), cnte = 0; }
inline void AddEdge(int u, int v, int w = 0) {
e[++cnte] = Edge(v, hd[u], w);
hd[u] = cnte;
}
inline int head(int u) { return hd[u]; }
inline int nt(int u) { return e[u].nt; }
inline int to(int u) { return e[u].to; }
inline int wt(int u) { return e[u].wt; }
};
int n, m;
int uid[MaxE], vid[MaxE];
Graph< MaxV, MaxE >G;
inline void Input() {
read(n);
int v;
for(int u = 1; u <= n; u++) {
read(v);
while(v) {
uid[++m] = u, vid[m] = v;
G.AddEdge(u, v);
read(v);
}
}
}
int dfn[MaxV], low[MaxV], cntd;
stack<int >stk; int instk[MaxV];
int cntc, col[MaxV];
vector<int >clb[MaxV];
void Tarjan(int u) {
dfn[u] = low[u] = ++cntd;
stk.push(u), instk[u] = 1;
for(int i = G.head(u); i; i = G.nt(i)) {
int v = G.to(i);
if(!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(instk[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if(low[u] == dfn[u]) {
++cntc;
int v = stk.top(); stk.pop();
while(v != u) {
col[v] = cntc;
instk[v] = 0;
clb[cntc].push_back(v);
v = stk.top(); stk.pop();
}
col[v] = cntc;
instk[v] = 0;
clb[cntc].push_back(v);
}
}
int inD[MaxV], otD[MaxV];
inline void Init() {
for(int i = 1; i <= m; i++) {
if(col[uid[i]] == col[vid[i]]) continue;
inD[col[vid[i]]]++; otD[col[uid[i]]]++;
}
}
inline void Work() {
for(int i = 1; i <= n; i++) {
if(dfn[i] == 0) {
Tarjan(i);
}
}
Init();
int cnt0 = 0, cnt1 = 0;
for(int i = 1; i <= cntc; i++) {
if(inD[i] == 0) {
cnt0++;
}
if(otD[i] == 0) {
cnt1++;
}
}
if(cntc == 1) printf("1\n0");
else printf("%d\n%d", cnt0, max(cnt0, cnt1));
}
int main() {
int T = 1;
while(T--) {
Input();
Work();
}
return 0;
}
|
