MYF

HDU 4857 逃生

Posted on | In | | Visitors

题目链接

HDU 4857

方法：反向拓扑排序(BFS+优先队列)

题目分析

解析

本题目不是单纯的拓扑排序，主要关注这句话：

负责人现在可以安排大家排队的顺序，由于收了好处，所以他要让1号尽量靠前，如果此时还有多种情况，就再让2号尽量靠前，如果还有多种情况，就让3号尽量靠前，以此类推。

因为拓扑排序是正向排序，如果要满足上面的条件，则需要使用priority_queue反向建图再反向输出。

拓扑排序(BFS版)个人理解

将所有入度为0的点全都push进队列，然后对队列中的每一个点u执行两个操作。1.将其排入topo数组之中，2.找对应的临接点v，并将这条边删除(表现为将v的入度减一)，如果此时v的入度为0了，则将v点Push进队列。当队列为空时，topo数组即为排好序的序列。

代码

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
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define PI acos(-1)
#define rt(n)       (i==n?'\n':' ')
#define debug         printf("Hi----------\n")
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 30005
int n,m;
vector<int>head[maxn];
int indegree[maxn];
int ans[maxn];
void bfs(){
    int index=n;
    priority_queue<int>q;
    for (int i=1; i<=n; i++) {
        if (indegree[i]==0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u=q.top();
        q.pop();
        int sz=head[u].size();
        for (int i=0; i<sz; i++) {
            int v=head[u][i];
            if (--indegree[v]==0) {
                q.push(v);
            }
        }
        ans[index--]=u;
    }
    return;
}
int main(){
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&m);
        for (int i=0; i<=n; i++) {
            head[i].clear();
            indegree[i]=0;
            ans[i]=0;
        }
        while (m--) {
            int x,y;
            scanf("%d%d",&x,&y);
            head[y].push_back(x);
            indegree[x]++;
        }
        bfs();
        for (int i=1; i<=n; i++) {
            printf("%d%c",ans[i],rt(n));
        }
    }
}