C++14(g++5.4) 解法, 执行用时: 412ms, 内存消耗: 740K, 提交时间: 2019-08-20 21:54:38

#include<bits/stdc++.h>

#define FOG(x,y,z) for(register int x=y,x##_=z;x<=x##_;++x)
#define DOG(x,y,z) for(register int x=y,x##_=z;x>=x##_;--x)
#define FOR(x,y,z) for(int x=y,x##_=z;x<=x##_;++x)
#define DOR(x,y,z) for(int x=y,x##_=z;x>=x##_;--x)
#define FOR_(x,y,z,s) for(int x=y,x##_=z;x<=x##_;x+=s)
#define FOR__(x,y,z) for(int x=y,x##_=z;x<=x##_;x<<=1)
#define EOR(x,y) for(int x##_=head[x],y=edge[x##_].e;x##_;y=edge[x##_=edge[x##_].to].e)
#define EGOR(x,y,z) for(int x##_=head[x],y=edge[x##_].e,z=edge[x##_].c;x##_;y=edge[x##_=edge[x##_].to].e,z=edge[x##_].c)

#define clr(x,y) memset(x,y,sizeof(x))
#define cpy(x,y) memcpy(x,y,sizeof(x))
#define szf(x) sizeof(x)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)

#define read2(x,y) read(x),read(y)
#define read3(x,y,z) read(x),read(y),read(z)
#define read4(x,y,z,w) read3(x,y,z),read(w)
#define reads(str) sf("%s",str)

#define ts (*this)
#define sf scanf
#define pf printf

#define ll long long
#define ull unsigned long long
#define db long double
#define ct clock_t
#define ck() clock()
#define rd rand()
#define rmx RAND_MAX
#define RD T*(rd*2-rmx)


using namespace std;

template<class T>bool tomin(T &x,T y){return y<x?x=y,1:0;}
template<class T>bool tomax(T &x,T y){return x<y?x=y,1:0;}
template<class T>void read(T &x){
	char c;
	x=0;
	int f=1;
	while(c=getchar(),c<'0'||c>'9')if(c=='-')f=-1;
	do x=(x<<3)+(x<<1)+(c^48);
	while(c=getchar(),c>='0'&&c<='9');
	x*=f;
}

const db Pi=acos(-1);
const int maxn=2005;
const int maxm=10005;
int n,m;
int A[maxn];
namespace P30{
	bool eg[maxn][maxn];
	bool vis[maxn];
	int s[maxn];
	bool ans;
	int mn[maxn];
	int res[maxn];
	bool Check(int x,int p){
		if(vis[x])return 0;
		if(p>A[x])return 0;
		FOR(i,1,p-1)if(eg[x][s[i]])return 0;
		return 1;
	}
	void dfs(int x){
		if(x==n+1){
			if(!ans)FOR(i,1,n)res[i]=s[i];
			ans=1;
			FOR(i,1,n)tomin(mn[s[i]],i);
			return;
		}
		FOR(i,1,n)if(Check(i,x)){
			vis[i]=1;
			s[x]=i;
			dfs(x+1);
			vis[i]=0;
		}
	}
	void solve(){
		int x,y;
		FOR(i,1,m){
			read2(x,y);
			eg[x][y]=1;
		}
		clr(mn,67);
		dfs(1);
		FOR(i,1,n){
            pf("%d",mn[i]);
            if(i<n)putchar(' ');
        }
	}
}
namespace P100{
	struct Edge{
		int e,to;
	}edge[maxm];
	int deg[maxn],Deg[maxn];
	int head[maxn],tot;
	void Add(int x,int y){
		edge[++tot]=(Edge){y,head[x]};
		head[x]=tot;
		Deg[y]++;
	}
	struct node{
		int u,v;
		bool operator <(const node &A)const
		{
			return v<A.v;
		}
	}V[maxn];
	priority_queue<node>q;
	int stk[maxn],top;
	int solve(int s){
		cpy(deg,Deg);
		deg[s]=n;
		while(!q.empty())q.pop();
		FOR(i,1,n)if(!deg[i])q.push(V[i]);
		int p=n;
		while(!q.empty()){
			int u=q.top().u,v=q.top().v;q.pop();
			if(v<p)return p;
			p--;
			EOR(u,v)if(!(--deg[v]))q.push(V[v]);
		}
		return p;
	}
	void solve(){
		int x,y;
		FOR(i,1,n)V[i]=(node){i,A[i]};
		while(m--){
			read2(x,y);
			Add(y,x);
		}
		cpy(deg,Deg);
		FOR(i,1,n)if(!deg[i])q.push(V[i]);
		while(!q.empty()){
			int u=q.top().u;q.pop();
			stk[++top]=u;
			EOR(u,v)if(!(--deg[v]))q.push(V[v]);
		}
		FOR(i,1,n){
            pf("%d",solve(i));
            if(i<n)putchar(' ');
        }
	}
}
int main(){
	srand(time(NULL));
	read2(n,m);
	FOR(i,1,n)read(A[i]);
	if(n<=10)P30::solve();
	else P100::solve();
	return 0;
}

C++(clang++11) 解法, 执行用时: 343ms, 内存消耗: 584K, 提交时间: 2020-10-22 12:41:10

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=2e3+5;
int n,m,a[N],c[N],deg[N],id[N],dfn;bool vis[N];
vector<int>adj[N],Ans;
priority_queue<pii>q;
int getans(int x){
	while(!q.empty())q.pop();
	memcpy(deg,c,sizeof(deg));
	for(int i=1;i<=n;i++)if(!deg[i])q.push(pii(a[i],i));
	int tot=0;
	while(!q.empty()){
		int u=q.top().second;q.pop();
		if(u==x)continue;
		if(n-tot>a[u])return n-tot;
		tot++;
		for(auto v:adj[u]){deg[v]--;if(!deg[v])q.push(pii(a[v],v));}
	}
	return n-tot;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),adj[v].pb(u),deg[u]++;
	memcpy(c,deg,sizeof(c));
	for(int i=1;i<=n;i++)if(!deg[i])q.push(pii(a[i],i));
	while(!q.empty()){
		int u=q.top().second;q.pop();Ans.pb(u);
		for(auto v:adj[u]){deg[v]--;if(!deg[v])q.push(pii(a[v],v));}
	}
	reverse(Ans.begin(),Ans.end());
	//for(auto u:Ans)printf("%d ",u);puts("");
	for(int i=1;i<=n;i++)printf("%d%c",getans(i)," \n"[i==n]);
	return 0;
}