P4376题解

· · 题解

核心算法&前置知识：拓扑排序+二分

此题解默认大家已经掌握关于以上算法的基础知识。

同时也默认大家会链式前向星建图点进这题的大佬肯定都会。

Part1：看题+手玩样例

遇到这种具有多种有关优先级条件的题，我们一般首先考虑按照他们的优先顺序进行建图，然后进行拓扑排序。

以本题样例为例，通过FJ的第一次观察结果可知，为奶牛们挤奶的优先级是 1 号奶牛 > 2 号奶牛 > 3 号奶牛，那我们就考虑建造这一个有向无环图（DAG）（实际上就是条链）：

那么结合FJ第二次观察的结果，优先级是 4 号奶牛 > 2 号奶牛，那么我们的图就变成了这样：

如果你用此图来跑拓扑排序的话，那么拓扑序会有两个，分别是 4\ 1\ 2\ 3 和 1\ 4\ 2\ 3。

那我们继续来结合FJ第三次观察的结果，此时我们的图变成了这样：

这时候，我们的图出现了环，意味着有几个条件是互相矛盾的，所以此时这张图并没有拓扑序。

既然有环的时候无解，那我们还得判断这个图是否带环，那我们到底该怎么判断呢？

Part2：拓扑排序黑科技：判环

我们以下面的这张有向有环图为例。

我们来按照拓扑排序的流程走一遍：此时我们先删掉入度为 0 的点（也就是 1 号点）， 现在这张图就成这样了：

此时所有的点入度都不为 0，也就是说，此时拓扑排序已经进行不下去了（没有任何点可以入队）。

我们知道，当这张图上所有的点都被删去时，拓扑排序才能进行下去，这也侧面说明这张图是一张有向无环图。如果拓扑排序进行不下去时，图上还有点没有被删，那么这张图一定是一张有环的图。

因此，我们只需要在拓扑排序结束之后，判断所有点的入度是否全部为 0，如果有不小于 1 个点的入度不为 0，则这张图一定有环。

代码：

    queue<int>q;
    for(int i=1;i<=n;i++)
        if(!in[i])
            q.push(i);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=head[now];i;i=a[i].nxt)
        {
            int to=a[i].v;
            in[to]--;
            if(!in[to])q.push(to);
        }
    }
    int tot=0;
    for(int i=1;i<=n;i++)
        if(!in[i])tot++;
    if(tot<n)return false;
    return true;

那这个时候我们就有了一个非常暴力的思路，既然FJ想要使题目中的 X 尽可能大，那我们就可以从 [1,M] 暴力枚举出 X 的最大大小（通过重新建图+判环），求出 X 之后就可以愉快的用拓扑排序+优先队列来跑出这个答案序列了！

但这样做时间复杂度肯定是爆炸的，这是一个时间复杂度为平方级别的做法。

那我们该怎么优化呢？

Part3：二分

一个显然的结论，如果一张图上有环，那么它无论加上任意数量条边，这张图依然会有环。如果一张图上无环，那么它无论删去任意数量条边，这张图必定没有环。

这不是废话吗。

所以我们发现，定义 Y\in [1,X)，定义 Z\in (X,M]，如果 X 符合要求，那么 Y 也必定符合要求。同样，如果X不符合要求，那么 Z 也必定不符合要求。

这便说明，求 X 的这个过程可以用二分来实现。

那这样我们就实现了这份暴力代码的优化。

Part4：完整代码

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=1e5+5;
int n,m,cnt,head[MAXN],in[MAXN];
vector<int>v[MAXN];
struct edge
{
    int v,nxt;
}a[MAXN*2];
void addedge(int u,int v)
{
    a[++cnt].v=v;
    a[cnt].nxt=head[u];
    head[u]=cnt;
}
void build(int x)
{
    cnt=0;
    memset(head,0,sizeof(head));
    memset(in,0,sizeof(in));
    for(int i=1;i<=x;i++)
    for(int j=0;j<v[i].size()-1;j++)
    {
        addedge(v[i][j],v[i][j+1]);
        in[v[i][j+1]]++;
    }
}
int check(int x)
{
    build(x);
    queue<int>q;
    for(int i=1;i<=n;i++)
        if(!in[i])
            q.push(i);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=head[now];i;i=a[i].nxt)
        {
            int to=a[i].v;
            in[to]--;
            if(!in[to])q.push(to);
        }
    }
    int tot=0;
    for(int i=1;i<=n;i++)
        if(!in[i])tot++;
    if(tot<n)return false;
    return true;
}
void get_ans(int x)
{
    build(x);
    priority_queue<int,vector<int>,greater<int> >q;//使用优先队列 保证这个拓扑序的字典序最小
    for(int i=1;i<=n;i++)
        if(!in[i])
            q.push(i);
    while(!q.empty())
    {
        int now=q.top();
        q.pop();
        cout<<now<<" ";
        for(int i=head[now];i;i=a[i].nxt)
        {
            int to=a[i].v;
            in[to]--;
            if(!in[to])q.push(to);
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int si;
        cin>>si;
        for(int j=1;j<=si;j++)
        {
            int x;
            cin>>x;
            v[i].push_back(x);
        }
    }
    int l=1,r=m;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))l=mid+1;
        else r=mid-1;
    }
    int ans;
    for(ans=r;ans<=l;ans++)if(check(ans))break;
    get_ans(ans);
    return 0;
}

Part5：P.S.

快速将图删除的方法：将 head 数组中的数值全部重置为 0，并且将 cnt 归 0。

二分时不知道 l 是正确答案还是 r 是正确答案？二分结束后用这几行代码：

    int ans;
    for(ans=r;ans<=l;ans++)if(check(ans))break;

这样即可求出本次二分的正确答案。感觉有点暴力实际上跑的还是很快的，因为二分过后 l-r 的值非常小。