首页 > 代码库 > 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;}
View Code

 

BZOJ4010 HNOI2015 菜肴制作 拓扑排序+贪心