原文地址

题目分析

题意

老板发工资，可是要保证发的工资数满足每一个人的期望，比方A期望工资大于B，仅仅需比B多1元钱就可以。老板发的最低工资为888元。输出老板最少发的工资总数。若是无法满足大家的期望，则输出-1。

分析

非常明显这是一个拓扑问题。若存在环则无法满足大家的期望。若按常理，A>B,则可能会建立A指向B的有向边。此题不然，由于我们仅仅知道最少的钱数是888，所以从小到大进行拓扑排序更为恰当。所以是建立B指向A的有向边。

此之为逆拓扑排序。由于这样处理后排序的结果与原先拓扑排序的顺序相反。

以图论观点来看，若为邻接矩阵存储就视作了矩阵的逆置。

链式前向星

链式前向星是图的一种存储方式，事实上质是邻接表的静态存储。

关于链式前向星的很多其它介绍。可移步《深度理解链式前向星》。

吐槽，链式前向星并不是学术上的术语，貌似是国内网友的起名智慧。。因此国外没有这种术语。只是这个词在国内还是有认可度的。

我的代码

用了点小技巧，比方static变量。还有重载构造函数等等。因此跑了359ms（g++）43ms（c++）。

。

囧。重度追求效率的童鞋可无视。本代码重在谈思路。

。 } } int sum=n*888; for(int i=1;i<=n;i++) { if(reward[i]<0) { cout<<-1<<endl;//假设奖金（工资）数组reward中还有-1存在，说明有环。 return; } sum+=reward[i]; } cout<<sum<<endl; } int main() { int i,j; while(cin>>n>>m) { memset(in,0,sizeof in); memset(head,-1,sizeof head); memset(reward,-1,sizeof reward); for(int t=0;t<m;t++) { cin>>i>>j; add(j,i); in[i]++; } topo(); } }