Codeforces Round #455 (Div. 2) 909E. Coprocessor

题

　　OvO http://codeforces.com/contest/909/problem/E

　　CF455 div2 E

　　CF 909E

解

　　类似于拓扑排序地进行贪心，

　　对于 Ei=0 并且入度为 0 的点，创建一个缓冲队列，把这些点的影响到的点先放到缓冲队列中，然后等一次 coprocessor calls 计算完后统一处理，保证每次找 coprocessor calls 的集合的时候，缓冲队列为空

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <queue>

using namespace std;

const int N=1e5+44;

struct node{

    int u,v;

    int next;

}edge[2*N];

int head[N],num,tag[N];

int n,m;

int indg[N];

int que[N],lq,rq;

queue<int> dlt_wait;

void addedge(int u,int v)

{

    edge[num].u=u;

    edge[num].v=v;

    edge[num].next=head[u];

    head[u]=num++;

}

void init()

{

	num=0;

   	memset(head,-1,sizeof(head));

}

void dlt(int id)

{

	for(int i=head[id];i!=-1;i=edge[i].next)

		dlt_wait.push(edge[i].v);

}

void clean()

{

	int now;

	while(!dlt_wait.empty())

	{

		now=dlt_wait.front(),dlt_wait.pop();

		if(--indg[now]==0)

		{

			if(tag[now])

				que[++rq]=now;

			else

				dlt(now);

		}

	}

}

void solve()

{

	int tmp,now;

	int ans=0;

	lq=1,rq=0;

	while(!dlt_wait.empty())

		dlt_wait.pop();

	for(int i=0;i<n;i++)

		if(indg[i]==0)

		{

			if(tag[i])

				que[++rq]=i;

			else

				dlt(i);

		}

	clean();

	while(lq<=rq)

	{

		ans++;

		while(lq<=rq)

		{

			now=que[lq++];

			for(int i=head[now];i!=-1;i=edge[i].next)

				if(--indg[edge[i].v]==0)

				{

					if(tag[edge[i].v])

						que[++rq]=edge[i].v;

					else dlt(edge[i].v);

				}

		}

		clean();

	}

	printf("%d\n",ans);

}

int main()

{

	int a,b;

	memset(indg,0,sizeof(indg));

	init();

	scanf("%d%d",&n,&m);

	for(int i=0;i<n;i++)

		scanf("%d",&tag[i]);

	for(int i=0;i<m;i++)

	{

		scanf("%d%d",&a,&b);

		addedge(b,a);

		indg[a]++;

	}

	solve();

	return 0;

}