Luogu3243 - [HNOI2015]菜肴制作

2017/10/21

题目

知名美食家小 A 被邀请至 ATM 大酒店,为其品评菜肴。 ATM 酒店为小 A 准备了 N 道菜肴, 酒店按照为菜肴预估的质量从高到低给予1到N的顺序编号,预估质量最高的菜肴编号为1。

由于菜肴之间口味搭配的问题,某些菜肴必须在另一些菜肴之前制作,具体的,一共有 M 条形如 “i 号菜肴 ‘必须’ 先于 j 号菜肴制作” 的限制,我们将这样的限制简写为 。 现在,酒店希望能求出一个最优的菜肴的制作顺序,使得小 A能尽量先吃到质量高的菜肴:

也就是说,

(1)在满足所有限制的前提下,1 号菜肴”尽量“优先制作;
(2)在满足所有限制,1号菜肴”尽量“优先制作的前提下,2号菜肴”尽量“优先制作;
(3)在满足所有限制,1号和2号菜肴”尽量“优先的前提下,3号菜肴”尽量“优先制作;
(4)在满足所有限制,1 号和 2 号和 3 号菜肴”尽量“优先的前提下,4 号菜肴”尽量“优先制作;
(5)以此类推。

例1:共 4 道菜肴,两条限制 <3, 1>、<4, 1> ,那么制作顺序是 3,4,1,2。

例2:共 5道菜肴,两条限制 <5, 2>、<4, 3> ,那么制作顺序是 1,5,2,4,3。

现在你需要求出这个最优的菜肴制作顺序。无解输出”Impossible!“ (不含引号,首字母大写,其余字母小写)

100% 的数据满足 N, M <= 100000, D <= 3。

代码

注意到样例中有构成了环形依赖导致无解的情况,所以考虑求一个拓扑序。

正确求法是反图上倒着求字典序最大的拓扑序。

 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
70
71
72
73
74
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int SIZ = 200000 + 1007;

struct tgno {
    int v; tgno *n;
} POOL[SIZ], *Head[SIZ]; int ppos;
int In[SIZ];

int N, M;

void addEdge(int u, int v) {
    POOL[ppos].v = v;
    POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
    In[v]++;
}

bool noans = false;
int ans[SIZ]; int apos = 0;
void topo_sort() {
    apos = 0;
    
    priority_queue<int> pq;
    
    for(int i=1;i<=N;i++) {
        if(!In[i]) pq.push(i);
    }
    
    int cnt = 0;
    while(!pq.empty()) {
        int u = pq.top(); pq.pop(); cnt++;
        ans[apos++] = u;
        
        typedef tgno* It;
        for(It i=Head[u];i;i=i->n) {
            In[i->v]--;
            if(!In[i->v]) pq.push(i->v);
        }
    }
    
    if(cnt != N) noans = true;
}

int main() {
    int D; scanf("%d", &D);
    
    while(D--) {
        scanf("%d %d", &N, &M);
        memset(POOL, 0, sizeof(POOL));
        memset(Head, 0, sizeof(Head)); ppos = 0;
        memset(In, 0, sizeof(In)); noans = false;
        
        for(int i=1, u, v;i<=M;i++) {
            scanf("%d %d", &u, &v);
            addEdge(v, u);
        }
        
        topo_sort();
        
        if(noans) puts("Impossible!");
        else {
            for(int i=apos-1;i>=0;i--) {
                printf("%d ", ans[i]);
            }
            puts("");
        }
    }
}