解題區/解題區 - UVa

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