bzoj4010: [HNOI2015]菜肴制作

本文主要是介绍bzoj4010: [HNOI2015]菜肴制作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4010

思路：显然最小字典序是错误的，那么应该怎么求？

直接选小的在前不一定对，但是如果没有都没有后继，大的在后面一定是对的

所以考虑倒着DP，求出最大拓扑序，反向输出即可

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=200010;
using namespace std;
int cas,n,m,pre[maxn],now[maxn],son[maxn],in[maxn],num,ans[maxn],tot;
struct li{int x,y;}l[maxn];
bool cmp(li a,li b){return a.x==b.x?a.y<b.y:a.x<b.x;}
void add(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b,in[b]++;}
void clear(){tot=num=0,memset(now,0,sizeof(now)),memset(in,0,sizeof(in));}bool topsort(){int cnt=n;priority_queue<int> q;for (int i=1;i<=n;i++) if (!in[i]) q.push(i);while (!q.empty()){int x=q.top();ans[cnt--]=x,q.pop();for (int y=now[x];y;y=pre[y]) if (!(--in[son[y]])) q.push(son[y]);}return !cnt;
}int main(){scanf("%d",&cas);while (cas--){scanf("%d%d",&n,&m),clear();for (int i=1;i<=m;i++) scanf("%d%d",&l[i].x,&l[i].y);sort(l+1,l+1+m,cmp);for (int i=1;i<=m;i++) if (l[i].x!=l[i-1].x||l[i].y!=l[i-1].y) add(l[i].y,l[i].x);if (!topsort()) puts("Impossible!");else {for (int i=1;i<=n;i++) printf("%d ",ans[i]);puts("");}}return 0;
}

这篇关于bzoj4010: [HNOI2015]菜肴制作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---