2153: D.ly的排隊問題

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

Description

馬上要上體育課了，上體育課之前總歸是要排個隊的，ly作為班長，怎么排隊的問題只能由她來解決，但是馬上要上課了，ly又不清楚所有人的身高，她又不好意思問每個人的身高，因為這樣會顯的自己很不負責，于是她只能通過肉眼觀察...那么問題來了，她只能觀察出兩個人A和B誰高誰矮，但是她沒有辦法排出一個序列。
ly都已經幫你出了兩次主意贏過wjw，那么現在她需要你的幫助，你可以幫她嗎？
(ly會告訴你A和B誰高，如果A比B高，會用A>B來表示)

Input

只有一組數據，每個比較結果占一行，讀取到文件結束

Output

若輸入數據無解，則輸出"No Answer!",否則從高到低輸出每個人的名字，中間沒有分割符
若有多種情況，輸出字典序最小的答案

Sample Input

E>A A>S S>Y

Sample Output

EASY

解析：基礎的拓撲排序+priority_queue，優先隊列有一個好處就是可以直接進行我們規定的規則排序。這里有一個坑，輸入以EOF結束，所以我們每次輸入3個字符的時候要吃掉一個換行符，可以這樣寫scanf("? %c%c%c? ",&a,&x,&b);在%c后面留一個空格可以吃掉回車，就是因為少吃掉一個\n wrong一發

#include<bits/stdc++.h> using namespace std;const int maxn=5000+10; int vis[maxn],vv[maxn]; int ans[maxn]; vector<int> v[maxn]; int main() {char a,b,x;int cnt=0,t=0;memset(vis,0,sizeof(vis));memset(vv,0,sizeof(vv));//printf("%d",(int)'Z');for(int i=0; i<maxn; i++)v[i].clear();while(~scanf(" %c%c%c ",&a,&x,&b)){if(vv[a]==0){vv[a]=1;cnt++;}if(vv[b]==0){vv[b]=1;cnt++;}if(x=='>'){v[a].push_back(b);vis[b]++;}else{v[b].push_back(a);vis[a]++;}//printf("%d %d\n",vv[a],vv[b]);}priority_queue<int,vector<int>,greater<int> >q;while(!q.empty())q.pop();for(int i=0; i<500; i++){if(vv[i]==1&&vis[i]==0)q.push(i);}t=0;while(!q.empty()){int u=q.top();q.pop();ans[t++]=u;for(int i=0; i<v[u].size(); i++){vis[v[u][i]]--;if(vis[v[u][i]]==0)q.push(v[u][i]);}}if(t!=cnt){printf("No Answer!\n");}else {for(int i=0; i<t; i++)printf("%c",ans[i]);printf("\n");} }

總結

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

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