记录编号	167242	评测结果	AAAAAAAAAA
题目名称	471.[NOI 2010]航空管制	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.133 s
提交时间	2015-06-22 18:51:28	内存使用	0.76 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

#define N 4010

using namespace std;

int n,m,totE,tot;
int a[N],nt[N],ind[N],pre[N],g[N],topn[N],b[N],pos[N];
int cntd[N];
bool v[N],rem[N];
queue<int> q;

struct edge{
	int x,to;
}E[N*10];

void ade(int x,int y){
	E[++totE]=(edge){y,g[x]}; g[x]=totE; ind[y]++;
}

bool cmp(int x,int y){
	return a[x]<a[y];
}

void dfs(int x){
	v[x]=1;
	for(int i=g[x];i;i=E[i].to){
		if(!v[E[i].x]) dfs(E[i].x);
	}
}

int get(){
	for(int i=1;i<=n;i++) rem[i]=0;
	int j=1;
	pos[0]=0;
	for(int i=1;i<=n;i++){
		while(j<=n && rem[nt[j]]) j++;
		if(j<=n){
			rem[nt[j]]=1;
			pos[++pos[0]]=nt[j];
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",pos[i]);
	printf("\n");
}

int find(int x){
	int ans=0;
	for(int i=1;i<=n;i++) v[i]=0;
	dfs(x);
	for(int i=1;i<=n;i++) if(v[i]) ans++;
	int tmp=ans;
	for(int i=1;i<=n;i++){
		if(v[nt[i]]) continue;
		tmp++;
		if(a[nt[i]]<=ans) ans++;
		else if(a[nt[i]]<tmp)
			ans=a[nt[i]]+1;
	}
	return ans;
}

int main(){
	freopen("plane.in","r",stdin);
	freopen("plane.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++) nt[i]=i;
	int x,y;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		ade(y,x);
	}
	for(int i=1;i<=n;i++)
		if(!ind[i]){
			q.push(i);
			v[i]=1;
		}
	while(!q.empty()){
		int x=q.front(); q.pop();
		topn[++topn[0]]=x;
		for(int i=g[x];i;i=E[i].to){
			int p=E[i].x;
			a[p]=min(a[p],a[x]-1);
			if((--ind[p])==0) q.push(p);
		}
	}
	sort(nt+1,nt+n+1,cmp);
//	get();
	for(int i=1;i<=n;i++) pre[i]=find(i);
	for(int i=1;i<=n;i++) printf("%d ",pre[i]);
	printf("\n");
	return 0;
}