UVa 12648 - Boss

contents

  1. 1. Problem
  2. 2. Sample Output
  3. 3. Sample Output
  4. 4. Solution

Problem

給一個管理階層圖 (DAG),一名員工可能被很多上司管理

  • 員工之間可能會交換職位
  • 詢問某名員工最年輕的上司年紀為何 (包含上司的上司 …)

Sample Output

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
7 8 9
21 33 33 18 42 22 26
1 2
1 3
2 5
3 5
3 6
4 6
4 7
6 7
P 7
T 4 2
P 7
P 5
T 1 4
P 7
T 4 7
P 2
P 6
6 5 6
10 20 30 40 50 60
1 5
1 4
3 6
2 5
4 5
P 1
P 5
P 6
T 1 6
P 1
P 4

Sample Output

1
2
3
4
5
6
7
8
9
10
11
18
21
18
18
*
26
*
10
30
30
60

Solution

粗劣一點暴力將圖的上司全找到,接著使用映射將員工和年齡的關係圖修正。

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
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
int visited[512];
int age[512];
vector<int> g[512], boss[512];
void dfs(int u, int em) {
visited[u] = 1, boss[em].push_back(u);
for(int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if(visited[v]) continue;
dfs(v, em);
}
}
int main() {
int N, M, I, x, y, em;
char cmd[10];
while(scanf("%d %d %d", &N, &M, &I) == 3) {
for(int i = 1; i <= N; i++) {
scanf("%d", &age[i]);
g[i].clear(), boss[i].clear();
}
for(int i = 0; i < M; i++) {
scanf("%d %d", &x, &y);
g[y].push_back(x);
}
int mp[512];
for(int i = 1; i <= N; i++) {
mp[i] = i;
memset(visited, 0, sizeof(visited));
visited[i] = 1;
for(int j = 0; j < g[i].size(); j++)
if(!visited[g[i][j]])
dfs(g[i][j], i);
}
for(int i = 0; i < I; i++) {
scanf("%s", cmd);
if(cmd[0] == 'P') {
scanf("%d", &em);
int ret = 0x3f3f3f3f;
em = mp[em];
for(int i = 0; i < boss[em].size(); i++)
ret = min(ret, age[boss[em][i]]);
if(ret == 0x3f3f3f3f)
puts("*");
else
printf("%d\n", ret);
} else {
scanf("%d %d", &x, &y);
swap(age[mp[x]], age[mp[y]]);
swap(mp[x], mp[y]);
}
}
}
return 0;
}