首页 > 其他 > 详细

bzoj 4010 [HNOI2015]菜肴制作——贪心

时间:2018-12-18 01:18:29      阅读:147      评论:0      收藏:0      [点我收藏+]

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4010

和 bzoj 2535 差不多。因为当前怎么决策与该点后面连的点的标号情况有关,所以按倒着的拓扑序决策。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+5;
int T,n,m,hd[N],xnt,to[N],nxt[N];
int deg[N],ans[N]; bool vis[N],ins[N],flag;
int dfn[N],low[N],tim;
priority_queue<int> q;
int Mn(int a,int b){return a<b?a:b;}
int rdn()
{
  int ret=0;bool fx=1;char ch=getchar();
  while(ch>9||ch<0){if(ch==-)fx=0;ch=getchar();}
  while(ch>=0&&ch<=9)ret=ret*10+ch-0,ch=getchar();
  return fx?ret:-ret;
}
void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;deg[y]++;}
void dfs(int cr)
{
  vis[cr]=ins[cr]=1;dfn[cr]=low[cr]=++tim;
  for(int i=hd[cr],v;i;i=nxt[i])
    if(!vis[v=to[i]])dfs(v),low[cr]=Mn(low[cr],low[v]);
    else if(ins[v]){flag=1;return;}
  ins[cr]=0;
}
int main()
{
  T=rdn();
  while(T--)
    {
      n=rdn();m=rdn(); xnt=0;flag=0;
      memset(hd,0,sizeof hd);memset(deg,0,sizeof deg);
      for(int i=1,u,v;i<=m;i++)
    u=rdn(),v=rdn(),add(v,u);
      memset(vis,0,sizeof vis);memset(ins,0,sizeof ins);
      tim=0;
      for(int i=1;i<=n;i++){if(!vis[i])dfs(i);if(flag)break;}
      if(flag){puts("Impossible!");continue;}
      for(int i=1;i<=n;i++)if(!deg[i])q.push(i);
      int p0=n;
      while(q.size())
    {
      int k=q.top();q.pop();
      ans[p0--]=k;
      for(int i=hd[k],v;i;i=nxt[i])
        if(!(--deg[v=to[i]]))q.push(v);
    }
      for(int i=1;i<=n;i++)printf("%d ",ans[i]);puts("");
    }
  return 0;
}

 

[HNOI2015]菜肴制作

bzoj 4010 [HNOI2015]菜肴制作——贪心

原文:https://www.cnblogs.com/Narh/p/10134751.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!