题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2535
把图反向，拓扑排序一下，用并查集维护当前权值能放置的最大位置。对于第二问，就相当于我把点i ban掉然后去找最后一个!ans[i]的位置。那么第一问就哪个点都不ban而已。
#include<cstring> #include<cctype> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define ll long long #define maxn 2005 #define mm int(1e9+7) using namespace std; struct edge{int obj,pre; }e[200500]; int ans[maxn],mn[maxn],d[maxn],t[maxn],head[maxn],dd[maxn],fa[maxn],q[maxn]; int n,m,x,y,tot,cnt,ban; void insert(int x,int y){ e[++tot].obj=y; e[tot].pre=head[x]; head[x]=tot; } int read(){ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } int get(int x){ if (fa[x]==x) return x; return fa[x]=get(fa[x]); } void dp(int ban){ rep(i,1,n) d[i]=dd[i],fa[i]=i,ans[i]=0,mn[i]=min(n,t[i]); cnt=0; rep(i,1,n) if (!d[i]) q[++cnt]=i; while (cnt){ int u=q[cnt--]; if (u==ban) continue; int pos=get(mn[u]); ans[pos]=u; fa[pos]=pos-1; for (int j=head[u];j;j=e[j].pre){ int v=e[j].obj; d[v]--; mn[v]=min(mn[v],mn[u]); if (!d[v]) q[++cnt]=v; } } } int main(){ n=read(); m=read(); rep(i,1,n) t[i]=read(); rep(i,1,m){ x=read(); y=read(); insert(y,x); dd[x]++; } dp(0); rep(i,1,n-1) printf("%d ",ans[i]); printf("%d ",ans[n]); rep(i,1,n){ dp(i); down(j,n,1) if (!ans[j]) { printf("%d%c",j,i==n?' ':' '); break; } } return 0; }