题意

题目链接

这里要注意的是，前继任务已经被执行过了的任务和前继任务被放进副处理器处理的任务是可以一次同时处理的，这也是题面中 “或” 的含义。另外， $0$ 表示只能在主处理器中处理， $1$ 表示只能在副处理器中处理。最后千万要注意，题目中所给的关系是前一个处理的前提是后一个被处理了，不要搞反。

解析

首先题面告诉我们这是一张 DAG，很容易就会想到拓扑。再观察题面，我们发现题目要求我们尽可能少的使用副处理器，换言之，就是让我们每次尽可能先不处理需要副处理器的任务，待到不得不处理时再一次性处理，这样可以使得我们每次处理掉的需要副处理器的任务尽可能多，且使用副处理器的次数尽可能少。

这很显然就是贪心了。

于是我们就用拓扑排序的方法，每一次先把主处理器能够处理的任务都处理掉，处理完后，再一次性处理目前能够处理的所有需要副处理器的任务。注意，除了目前入度为 $0$ 的任务可以处理以外，在这些任务都被处理掉之后入度为 $0$ 的点满足 “前继任务被放进副处理器处理的任务” 这一条件，也是能够在同一次处理中被处理掉的。

于是代码就呼之欲出了。

代码

#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
int n,m,cnt,head[N];
int a[N],ru[N],ans;
struct edge{
    int to,next;
}e[N];
inline void add(int x,int y){
    e[++cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt;
}
 
queue<int> qmain,qco;
 
inline void topo(){
    for(int i=1;i<=n;i++){
        if(!ru[i]){
            if(!a[i]) qmain.push(i);
            else qco.push(i);
        }
    }
    while((!qmain.empty())||(!qco.empty())){
        while(!qmain.empty()){//优先处理主处理器能处理的 
            int u=qmain.front();
            qmain.pop();
            for(int i=head[u];i;i=e[i].next){
                int v=e[i].to;
                ru[v]--;
                if(!ru[v]){
                    if(!a[v]) qmain.push(v);
                    else qco.push(v);
                }
            }
        }
        if(!qco.empty())
            ans++;//如果需要副处理器处理的话就将处理次数+1 
        while(!qco.empty()){//一次性把所有能一起处理的任务都处理掉 
            int u=qco.front();
            qco.pop();
            for(int i=head[u];i;i=e[i].next){
                int v=e[i].to;
                ru[v]--;
                if(!ru[v]){
                    if(!a[v]) qmain.push(v);
                    else qco.push(v);
                }
            }
        }
    }
}
 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1,y,x;i<=m;i++){
        scanf("%d%d",&y,&x);//注意输入顺序与实际操作要求顺序相反 
        add(x+1,y+1);ru[y+1]++;
    }
    topo();
    printf("%d",ans);
    return 0;
}