首页 > 代码库 > BZOJ4010 HNOI2015 菜肴制作 拓扑排序+贪心
BZOJ4010 HNOI2015 菜肴制作 拓扑排序+贪心
题意:给定限制条件(a,b)表示a必须在b之前,求所有合法序列中,小的数尽量在前面的方案
题解:首先我们根据限制条件建反向图,然后在反向图上求字典序最小的拓扑序(队列改为堆),逆序输出即可。
#include <queue>#include <functional>#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int MAXN=100000+2;struct HASH{ int u; HASH *next; HASH(){} HASH(int _u,HASH *_next):u(_u),next(_next){}}*table[MAXN],mem[MAXN*2];int N,M,Q,cnt,ans[MAXN],degree[MAXN];priority_queue<int> q;void Insert(int u,int v){ table[u]=&(mem[cnt++]=HASH(v,table[u]));}void Topology_Sort(){ while(!q.empty()) q.pop(); for(int i=1;i<=N;i++) if(!degree[i]) q.push(i); while(!q.empty()){ ans[++cnt]=q.top(),q.pop(); for(HASH *p=table[ans[cnt]];p;p=p->next){ degree[p->u]--; if(!degree[p->u]) q.push(p->u); } }}int main(){ scanf("%d",&Q); while(Q--){ memset(table,0,sizeof(table)); memset(degree,0,sizeof(degree)); cnt=0; scanf("%d %d",&N,&M); for(int i=1,u,v;i<=M;i++){ scanf("%d %d",&u,&v); Insert(v,u),degree[u]++; } cnt=0,Topology_Sort(); if(cnt!=N) printf("Impossible!\n"); else{ for(int i=N;i;i--) printf("%d ",ans[i]); printf("\n"); } } return 0;}
BZOJ4010 HNOI2015 菜肴制作 拓扑排序+贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。