hdu2647 逆拓撲，鍊式前向星。原文位址題目分析我的代碼

老闆發工資，可是要保證發的工資數滿足每一個人的期望，比方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();

本文轉自mfrbuaa部落格園部落格，原文連結：http://www.cnblogs.com/mfrbuaa/p/5123623.html，如需轉載請自行聯系原作者