记录编号	360560	评测结果	AAAAAAAAAA
题目名称	471.[NOI 2010]航空管制	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.128 s
提交时间	2016-12-30 10:17:15	内存使用	1.11 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2010,M=1e5+10;
int n,m,a[N],k[N],in[N],ans[N];
int w[M],head[N],tail[N],next[M];
void add(int f,int t){
	static int cnt=0;
	w[++cnt]=t;in[t]++;
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
}
int q[N],r,cnt;//存拓扑序 
bool vis[N];
bool cmp(const int x,const int y){
	return k[x]<k[y];
}
void dfs(int x){
	if (vis[x]) return;
	vis[x]=1;cnt++;
	for (int i=head[x];i;i=next[i]) dfs(w[i]);
}
void solve(int x){
	for (int i=1;i<=n;i++) vis[i]=0;
	cnt=0;dfs(x);
	int now=cnt;
	for (int i=1;i<=n;i++){
		int v=a[i];
		if (vis[v]) continue;
		now++;
		if (k[v]<=cnt) cnt++;else
		if (k[v]<now) cnt=k[v]+1;
	}
	printf("%d ",cnt);
}
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",&k[i]),a[i]=i;
	for (int i=1;i<=m;i++){
		int f,t;
		scanf("%d%d",&f,&t);
		add(t,f);
	}
	for (int i=1;i<=n;i++)
	if (!in[i]) q[++r]=i;
	for (int i=1;i<=r;i++){
		int v=q[i];
		for (int j=head[v];j;j=next[j]){
			int u=w[j];
			k[u]=min(k[u],k[v]-1);
			if (!--in[u]) q[++r]=u;
		}
	}
	sort(a+1,a+n+1,cmp);
	for (int i=1;i<=n;i++) solve(i);
	puts("");
	return 0;
}