UVa 13015 - Promotions

contents

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

Problem

$N$ 名員工,他們彼此之間會推薦、相互提拔對方,因此站在公司的角度來看,提拔順序不能違反這張圖的上下關係,亦即若要提拔某人,其推薦他的人全部都要被提拔。請問若要提拔 $A$ 個人,有哪些人一定會被提拔,同樣的,回答提拔 $B$ 個人的情況,最後回答,若提拔 $B$ 個人,誰一定不會被提拔?

Sample Input

1
2
3
4
5
6
7
8
9
3 4 7 8
0 4
1 2
1 5
5 2
6 4
0 1
2 3
4 5

Sample Output

1
2
3
2
4
3

Solution

一定是張 DAG,否則不能處理。對於輸入多存一張反向圖,接著每一次都去找其下屬節點有多少個,藉此構造出任何提拔方案中,最好和最差排名為多少。處理全部排名計算 $\mathcal{O}(V^2 E)$

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
#include <bits/stdc++.h>
using namespace std;
// O(VE)
const int MAXN = 5005;
int A, B, E, P;
vector<int> G[MAXN], invG[MAXN];
int used[MAXN] = {}, cases = 0;
int dfs(int u, vector<int> g[]) {
if (used[u] == cases) return 0;
used[u] = cases;
int ret = 1;
for (auto v : g[u])
ret += dfs(v, g);
return ret;
}
int main() {
int x, y;
while (scanf("%d %d %d %d", &A, &B, &E, &P) == 4) {
for (int i = 0; i < E; i++)
G[i].clear(), invG[i].clear();
// Must DAG
for (int i = 0; i < P; i++) {
scanf("%d %d", &x, &y);
G[x].push_back(y), invG[y].push_back(x);
}
int retA = 0, retB = 0, retN = 0;
for (int i = 0; i < E; i++) {
int worst, best;
cases++;
worst = E - dfs(i, G) + 1;
cases++;
best = dfs(i, invG);
if (worst <= A) retA++;
if (worst <= B) retB++;
if (best > B) retN++;
}
printf("%d\n%d\n%d\n", retA, retB, retN);
}
return 0;
}