題目： UVa - 924 - Spreading The News
題目說明
在一個組織裡面散布消息，組織裡面的員工都有跟自己比較好的朋友，每位員工收到消息後會在隔天跟所有比較好的朋友說，現在將消息告訴一位員工，求在哪一天消息會被最多原本不知道的人知道。
Input： 不太好解釋，所以直接拿題目的 Sample I/O 來解釋。
1
2
3
4
5
6
7
8
9
10
11
| 6 表示有 6 位員工 ( 序號為 0 ~ 5 )
2 1 2 第零位員工的朋友，第一個整數為朋友數，後面接的是朋友的序號，意思為，若 0 號收到消息，會在隔天跟 1 號還有 2 號說
2 3 4 第一位員工的朋友，第一個整數為朋友數，後面接的是朋友的序號，意思為，若 1 號收到消息，會在隔天跟 3 號還有 4 號說
3 0 4 5 .
1 4 .
0 .
2 0 2 第一位員工的朋友，第一個整數為朋友數，後面接的是朋友的序號，意思為，若 5 號收到消息，會在隔天跟 0 號還有 2 號說
3 幾組測試
0 若先將消息跟 0 號員工說
4 若先將消息跟 4 號員工說
5 若先將消息跟 5 號員工說
|
Output： 輸出在哪一天消息會被最多原本不知道的人知道的人數及天數，如答案若為 3 2，表示在第二天有 3 個原本不知道的人知道了。
解題思路
先根據朋友的關係建圖，之後 BFS 求解，由於題目要求每天的傳播人數，所以每次都取在隊列中的所有人進行傳播，模擬一天的情況。
參考解法
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
| #include <iostream>
#include <unordered_set>
#include <vector>
#include <queue>
using namespace std;
static auto __ = []
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();
vector<vector<int>> G;
unordered_set<int> visited;
void bfs(int n)
{
queue<int> q;
q.push(n);
visited.insert(n);
int day = 1, cnt;
pair<int, int> _max;
while (!q.empty())
{
int size = q.size();
cnt = 0;
while (size--)
{
int u = q.front();
q.pop();
for (auto& v : G[u])
{
if (visited.count(v)) continue;
q.push(v);
visited.insert(v);
++cnt;
}
}
if (cnt > _max.second) _max = { day, cnt };
++day;
}
if (!_max.second) cout << "0\n";
else cout << _max.second << " " << _max.first << '\n';
}
int main()
{
int E;
while (cin >> E)
{
G.assign(E, vector<int>());
int n, v;
for (int u = 0; u < E; ++u)
{
cin >> n;
while (n--) cin >> v, G[u].push_back(v);
}
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
visited.clear();
bfs(n);
}
}
}
|
參考資料
UVA 924/SPREADING THE NEWS
UVa 924 - Spreading The News | NaiveRed’s Blog
