M_sea

洛谷3243 [HNOI2015]菜肴制作
LuoguBZOJ分析$25\mathrm{min}$切了此题qwq一开始我觉得,显然可以用拓扑排序来做,只要求字...
扫描右侧二维码阅读全文
20
2019/02

洛谷3243 [HNOI2015]菜肴制作

Luogu

BZOJ

分析

$25\mathrm{min}$切了此题qwq

一开始我觉得,显然可以用拓扑排序来做,只要求字典序最小的拓扑序列就行了。

然后$\color{red}{\mathrm{WA\ on\ \#Example\ 3}}$

于是冷静分析一波,发现要求的其实是字典序最大倒序的拓扑序列。

具体来讲,对于每一个条件 $(u,v)$ ,从 $v$ 向 $u$ 连边,然后再跑一遍拓扑排序求出字典序最大的拓扑序列,最后倒序输出即可。

正确性比较显然。

字典序的话,用堆来维护。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

struct Edge { int v,nxt; } e[N];
int head[N],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int n,m,tot=0;
int deg[N],vis[N],ans[N];

inline void Topsort() {
    /*初始化*/
    memset(vis,0,sizeof(vis)),tot=0;
    /*排序*/
    priority_queue<int> Q;
    for (re int i=1;i<=n;++i)
        if (!deg[i]) Q.push(i),vis[i]=1;
    while (!Q.empty()) {
        int u=Q.top(); Q.pop(); ans[++tot]=u;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; --deg[v];
            if (!deg[v]&&!vis[v]) Q.push(v),vis[v]=1;
        }
    }
    /*输出*/
    int flag=1;
    for (re int i=1;i<=n;++i)
        if (deg[i]) { flag=0; break; }
    if (flag) {
        for (re int i=n;i>=1;--i) printf("%d ",ans[i]);
        putchar('\n');
    }
    else puts("Impossible!");
}

int main() {
    int T=read();
    while (T--) {
        memset(head,0,sizeof(head)),cnt=0;
        memset(deg,0,sizeof(deg));
        n=read(),m=read();
        for (re int i=1;i<=m;++i) {
            int u=read(),v=read();
            addEdge(v,u); ++deg[u];
        }
        Topsort();
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 53 PM

2 条评论

  1. smy

    神仙吧,天天秒题

    1. M_sea
      @smy

      这题不是大氵题吗

发表评论