P3243 [HNOI2015]菜肴制作(拓扑排序)

P3243 [HNOI2015]菜肴制作

题目误导你正着做拓扑排序,然鹅你可以手造数据推翻它。于是就只能倒着做

我们开个优先队列,每次把可填的最大的编号取出来搞,最后倒着输出拓扑序就好辣

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define N 100005
int n, m, tp, Q[N], in[N];
int cnt,hd[N],nxt[N<<],ed[N],poi[N<<];
inline void add(int x,int y){
nxt[ed[x]]=++cnt, hd[x]=hd[x]?hd[x]:cnt,
ed[x]=cnt, poi[cnt]=y, ++in[y];
}
void bfs() {
priority_queue<int> h;
for (int i = ; i <= n; ++i)
if (!in[i]) h.push(i);
while (!h.empty()) {
int x = h.top(); h.pop();
Q[++tp] = x;
for(int i=hd[x];i;i=nxt[i]){
--in[poi[i]];
if(in[poi[i]]==) h.push(poi[i]);
}
}
}
int main() {
int T; scanf("%d",&T);
while(T--){
memset(in,,sizeof(in));
memset(hd,,sizeof(hd));
memset(ed,,sizeof(ed));
memset(nxt,,sizeof(nxt)); tp=cnt=;
scanf("%d%d", &n, &m);
for (int i = , f, t; i <= m; ++i)
scanf("%d%d", &f, &t),add(t,f);
bfs();
if (tp < n) {puts("Impossible!");continue;}
for (int i = n;i; --i) printf("%d ", Q[i]);
printf("\n");
}
return ;
}
上一篇:Visual Studio 2013 在使用 razor无智能提示的解决办法


下一篇:IPV4/IPV6双协议栈配置案例