2129: 卡勒沃夫之弱水路三千(提高型)

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?26??Solved:?8
[Submit][Status][Web Board]

Description

錦瑟年華誰與度 莫問情歸處 只影向斜陽 劍吼西風 欲把春留駐
天涯芳草無歸路 回首花無數 解語自銷魂 弱袂縈春 塵緣不相誤
......
在卡勒沃夫充滿文學殺傷力的聲音中，身處紫荊2號樓202B的四位遠近高低各不同的室友紛紛回憶起了各自波瀾起伏的過去，并對長在百草園，鄰有百花谷的現狀表達了各自的見解。
某Q："...我小學就開竅了...她的父母說我很好，但是...今天又和北林的聯系了..."
某X："...差點就成了，結果到學校了...這個方法放假了我去對我的同桌用！..."
某W："..."（千言萬語不言中，有大量的故事等待考古）
某Z："...為了來清華...咱們審美觀不一樣，不會搶..."
......
卡勒沃夫在這個不朽的夜話中搜集出了某人零散的歷任女友資料，為了強迫某人將他出的題目的標程交出，現在卡勒沃夫需要一個能將這些零散信息整合起來的 程序。伴隨著雄壯委婉動人的音樂，身為程序設計快男（超女）的你降臨了！卡勒沃夫正對著您做Orz狀并請求著："神牛啊~請施舍給我一段程序把~偶米頭 發~"。。

Input

第一行為一個不超過5的整數T，表示數據的組數。之后每組數據的一行為一個不超過100的整數n。之后n行每行有兩個用單個空格隔開的字符串（每個字符串只有英文大小寫字母，長度不超過10），為兩位mm的名字。每行第一個mm先于第二個mm成為某人的女友。
在這里我們假裝詛咒某人不會同時被兩個或兩個以上mm泡，某個mm拋棄了某人后不會再吃回頭草，同時卡勒沃夫深邃的洞察力使得他收集到了充足的信息以確定某人女友的先后順序。
在小數據組中出現的人物不超過13個

Output

輸出T行，每行對應一組數據，并按照mm們從先到后成為某人女友的順序輸出她們的名字，各個名字間用一個空格隔開。

Sample Input

22RY UnknownYSZ RY3tomorrow yestodaytomorrow todaytoday yestoday

Sample Output

YSZ RY Unknowntomorrow today yestoday

理解是有點難，認認真真看代碼 最近忙? 沒法寫那么多的解析了。

#include<cstdio> #include<iostream> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<set> #include<map> #include<queue> using namespace std; const int maxn=1000+5; map<string,int>n; map<int,string>m; vector<int>p[maxn]; int inde[maxn]; int t,x,k; void toposort() { queue<int> q; vector<int> ans; int i=0; while(inde[i]!=0)i++; q.push(i); while(!q.empty()) { int t=q.front(); ans.push_back(t); q.pop(); for(i=0; i<p[t].size(); i++) { inde[p[t][i]]--; if(inde[p[t][i]]==0) { q.push(p[t][i]); } } } for(i=0; i<ans.size()-1; i++) { cout<<m[ans[i]]<<" "; } cout<<m[ans[i]]<<endl; } int main() { cin>>t; while(t--) { cin>>x; string a,b; k=0; n.clear(); m.clear(); for(int i=0; i<maxn; i++) { p[i].clear(); } memset(inde,0,sizeof(inde)); while(x--) { cin>>a>>b; if(a==b)continue; if(!n.count(a)) { n[a]=k,m[k]=a,k++; } if(!n.count(b)) { n[b]=k,m[k]=b,k++; } p[n[a]].push_back(n[b]); inde[n[b]]++; } toposort(); } return 0; }

總結

以上是生活随笔為你收集整理的zcmu-2129（拓扑排序）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。