原题链接

考察：拓扑排序

错误思路1：

       先找到字典序最小的拓扑序列,再挨个赋值.

这个思路错在这道题需要的不是字典序最小的序列.而是字典序小的位置尽量靠前的序列.也就是说1 2 3...的位置要尽量考前.序号越小优先级越高

正确思路：

       这道题需要保证1 2 3...拓扑序列的位置应该尽量小.也就是说无论他在图里是多么后面.在拓扑序列里也要尽量靠前.要操作图内靠后的元素可以考虑逆向建图.在每次队列里将大元素放在队头,在赋值时再反转.这样序号小的元素就靠前了

 1 #include <iostream>
 2 #include <queue>
 3 #include <algorithm>
 4 #include <numeric>
 5 using namespace std;
 6 const int N = 210;//确定比赛名次那道题是仅仅是字典序最小 
 7 const int M = 40010;//这道题是要求序号小的位置尽量小 ,因此可能会有以大数在前面为代价. 
 8 int h[N],e[M],ne[M],d[N],idx,n,m,q[N],ans[N];
 9 void inits()
10 {
11     fill(d,d+N,0); fill(h,h+N,-1);
12     fill(ans,ans+N,0);
13     idx = 0;
14 }
15 void add(int a,int b)
16 {
17     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
18 }
19 void topsort()
20 {
21     int hh=0,tt = -1;
22     for(int i=1;i<=n;i++)  if(!d[i]) q[++tt] = i;
23     while(hh<=tt)
24     {
25         sort(q+hh,q+tt+1,greater<int>());
26         int x = q[hh++];
27         for(int i=h[x];i!=-1;i=ne[i])
28         {
29             int j = e[i];
30             if(--d[j]==0) q[++tt]=j;
31         }
32     }
33     if(tt!=n-1) printf("-1\n");
34     else{
35 //        for(int i=0;i<n;i++) printf("%d%c",q[i],i==n-1?'\n':' ');
36         reverse(q,q+n);
37         for(int i=0;i<n;i++) ans[q[i]] = i+1;
38         for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n?'\n':' ');
39     }
40 }
41 int main()
42 {
43    // freopen("in.txt","r",stdin);
44     int t;
45     scanf("%d",&t);
46     while(t--)
47     {
48         scanf("%d%d",&n,&m);
49         inits();
50         for(int i=1;i<=m;i++){
51             int x,y; scanf("%d%d",&x,&y);
52             add(y,x); d[x]++;
53         }
54         topsort();
55     }
56     return 0;
57 }