洛谷5603 小C与桌游

题意

给一个 $n(\le 5\times 10^5)$ 点 $m(\le 5\times 10^5)$ 边的有向无环图，求一个拓扑序满足拓扑序的前缀最大值最少/最多。

题解

最大的情况比较容易想到，从当前能走的点中选编号最小的点即可，用堆维护。

至于最小的情况，直接选最大的点拓展会喜提46分。很容易想到这种方法的问题所在，如果很小的一个点连着一个很大的点，把这两个都选了有可能最优。

考虑对贪心进行优化。如果当前最小的点不是前缀最大，那么先选不会影响答案，反而可能有更多选择；否则就选最大的。需要用两个堆维护。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

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

const int N=500005;
bool vis[N];
int n,m,a,b,in[N],in2[N];
vector <int> e[N];
priority_queue <int> mx;
priority_queue <int,vector<int>,greater<int> > mn;

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        e[a].emplace_back(b);
    }
    for (int i=1;i<=n;i++) //去掉重边
    {
        sort(e[i].begin(),e[i].end());
        auto ed=unique(e[i].begin(),e[i].end());
        e[i].erase(ed,e[i].end());
        for (auto x:e[i]) in[x]++;
    }
    for (int i=1;i<=n;i++) if (!in[i]) mx.emplace(i),mn.emplace(i);
    memcpy(in2,in,sizeof(in));
    int bef=0,ans=0;
    while (!mn.empty()) //最大的情况
    {
        int x=mn.top(); mn.pop();
        if (x>bef) ans++;
        if (ans==1919810) break;
        bef=max(bef,x);
        for (auto y:e[x])
        {
            in[y]--;
            if (!in[y]) mn.emplace(y);
        }
    }
    printf("%d\n",ans);
    bef=0; ans=0;
    for (int i=1;i<=n;i++) if (!in2[i]) mn.emplace(i);
    while (!mx.empty() || !mn.empty())
    {
        int x;
        if ((!mn.empty() && mn.top()<bef) || mx.empty()) x=mn.top(),mn.pop(); //选最小的
        else x=mx.top(),mx.pop(); //否则选最大的
        vis[x]=1;
        if (x>bef) ans++;
        if (ans==1919810) break;
        bef=max(bef,x);
        for (auto y:e[x])
        {
            in2[y]--;
            if (!in2[y]) mx.emplace(y),mn.emplace(y);
        }
        while (!mn.empty() && vis[mn.top()]) mn.pop(); //将选过的点退队
        while (!mx.empty() && vis[mx.top()]) mx.pop();
    }
    printf("%d",ans);
    return 0;
}