解題區►解題區 - UVa

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;
}