记录编号	60379	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]航空管制	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.109 s
提交时间	2013-05-23 21:21:09	内存使用	0.36 MiB

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<queue>
#include<deque>
#include<algorithm>
#include<cmath>
using namespace std;
const int SIZEN=2001;
int N,M;
vector<int> c[SIZEN];
int deg[SIZEN]={0};
int k[SIZEN]={0};
int numv;//numvisit
bool visit[SIZEN]={0};
int lis[SIZEN]={0};
void toposort(void){
	deque<int> Q;
	int i,x;
	for(i=1;i<=N;i++){
		if(!deg[i]) Q.push_back(i);
	}
	while(!Q.empty()){
		x=Q.front();Q.pop_front();
		for(i=0;i<c[x].size();i++){
			deg[c[x][i]]--;
			k[c[x][i]]=min(k[c[x][i]],k[x]-1);
			if(!deg[c[x][i]]) Q.push_back(c[x][i]);
		}
	}
}
void DFS(int x){
	if(visit[x]) return;
	visit[x]=true;numv++;
	int i;
	for(i=0;i<c[x].size();i++){
		DFS(c[x][i]);
	}
}
void singlenode(int x){
	memset(visit,0,sizeof(visit));
	numv=0;
	DFS(x);
	int i;
	int latest=numv;
	for(i=1;i<=N;i++){
		if(visit[lis[i]]) continue;
		latest++;
		if(k[lis[i]]<=numv){
			numv++;
		}
		else if(k[lis[i]]<latest){
			numv=k[lis[i]]+1;
		}
	}
	cout<<numv<<" ";
}
bool cmp(int a,int b){
	return k[a]<k[b];
}
void read(void){
	scanf("%d%d",&N,&M);
	int i,a,b;
	for(i=1;i<=N;i++) scanf("%d",&k[i]),lis[i]=i;
	for(i=1;i<=M;i++){
		scanf("%d%d",&a,&b);
		c[b].push_back(a);
		deg[a]++;
	}
	toposort();
	sort(lis+1,lis+1+N,cmp);
}
int main(){
	freopen("plane.in","r",stdin);
	freopen("plane.out","w",stdout);
	read();
	int i;
	for(i=1;i<=N;i++) singlenode(i);
	cout<<endl;
	return 0;
}