原题链接

考察：拓扑排序+逆向思维

看来之前的反向并查集还是要补一下,这道题同样是利用逆向思维,再次碰到我还是不会写

思路：

       这道题如果按正常的拓扑序列做,就难以得到正确答案,因为入度相同的点不一定都必须是同一报酬.但是如果我们将序列反转,那么求答案就容易得多.这样入度相同的点也不必是同一报酬.这些点会尽量被压入后面的位置,求答案也是从最少开始算起.而且这样也不必像正向一样必须离线计算

 1 #include <iostream>
 2 #include <queue>
 3 using namespace std;
 4 typedef long long ll;
 5 const int N = 20010;
 6 int h[N],e[N],ne[N],d[N],idx,n,m;
 7 void add(int a,int b)
 8 {
 9     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
10 }
11 ll topsort(ll ans)
12 {
13     queue<int> q; int low = 888,k=0;
14     for(int i=1;i<=n;i++) if(!d[i]) { q.push(i);k++; } 
15     while(!q.empty())
16     {
17         int sz = q.size();
18         ans += sz*low;low++; 
19         while(sz--)
20         {
21             int x = q.front();
22             q.pop();
23             for(int i=h[x];i!=-1;i=ne[i])
24             {
25                 int j = e[i]; d[j]--;
26                 if(!d[j]) { q.push(j);k++; } 
27             }
28         }
29     }
30     if(k==n) return ans;
31     else return -1;
32 }
33 int main()
34 {
35 //    freopen("in.txt","r",stdin);
36     while(scanf("%d%d",&n,&m)!=EOF)
37     {
38         ll ans = 0;
39         fill(d,d+N,0); fill(h,h+N/2,-1); idx = 0;
40         for(int i=1;i<=m;i++)
41         {
42             int x,y; scanf("%d%d",&x,&y);
43             add(y,x); d[x]++;
44         }
45         ans = topsort(ans);
46         printf("%lld\n",ans);
47     }
48     return 0;
49 }