?Problem 2227 郵票

Accept: 30????Submit: 68
Time Limit: 1000 mSec????Memory Limit : 32768 KB

?Problem Description

一天Bob收到一封信。Bob知道瓦羅蘭大陸的郵局從A城市送信到B城市，樂意使用從A城市到B城市的郵票（A, B）,或者使用從B城市到A城市的郵票（A, B），但是由于瓦羅蘭大陸的城市繁多，所以并不是所有城市之間都能直接發送接收信件，換句話說，某兩個城市想要通行郵件必須經過其他城市才行，但是郵局發送一次郵件的路途中從不會通過一座城市兩次。

現在在Bob的信封上有N個郵票，Bob想知道這封信件是如何周轉到達他手中的。

?Input

題目有多組數據。

每組數據第一行包含一個整數，N ( 2 <= N <= 1e5)，代表信件上的N封郵票。

接下有N行數據。第 i 行數據包含兩個整數 ui，vi，代表從城市ui發送到城市vi的郵票，ui代表城市的編號，每個城市的編號互不相同，(ui != vi ，1 <= ui, vi <= 1e9)。

輸入數據保證有解。

?Output

每組樣例的結果輸出為一行， 每行包括N+1個被空格隔開的整數，代表著信件依次經過的城市編號。

若有多組可行答案，輸出字典序最小的那組答案。

?Sample Input

21 100100 233 1100 23 2

?Sample Output

1 100 21 3 2 100

?Source

FOJ有獎月賽-2016年4月（校賽熱身賽）
Submit??Back??Status??Discuss

思路：通過題意我們可以知道在輸入數據中值只出現一次的便是起點或者終點(肯定只有兩個點，因為該題的路徑就是一條鏈)，因為輸出的是字典序最小的所以那兩個點中值小的為起點而值相對大的為終點，但1 <= ui, vi <= 1e9，不能開那么大的數組，用STL中的map來離散化就可以了。找到起點和終點后，用STL中的set來二分通過當前路徑的終點去查找起點，并打印路徑。做了這題后，頓時感覺STL的強大。。Orz

代碼：

#include <cstdio> #include <cstring> #include <utility> #include <map> #include <algorithm> #include <vector> #include <set> using namespace std; typedef long long ll; #define maxn (int)1e5 pair<int,int>point[maxn]; set<pair<int,int> >s1; map<int,int>mp1,mp2,mp3; int main() { #ifdef CDZSC_Junefreopen("t.txt","r",stdin); #endif // CDZSC_Juneint n,p;while(~scanf("%d",&n)){mp1.clear();mp2.clear();s1.clear();mp3.clear();p = 1;for(int i = 0; i<n; i++){scanf("%d%d",&point[i].first,&point[i].second);s1.insert(point[i]);s1.insert(make_pair(point[i].second, point[i].first));//因為路徑的雙向的if(mp1[point[i].first] == NULL){mp1[point[i].first] = p;mp2[p] =point[i].first; mp3[p] = 1;p++;}else{mp3[mp1[point[i].first]]++;}if(mp1[point[i].second] == NULL){mp1[point[i].second] = p;mp2[p] =point[i].second; mp3[p] = 1;p++;}else{mp3[mp1[point[i].second]]++;}}int s = -1,t = -1;for(int i = 0 ;i<p; i++){//只出現一次的為起點或終點if(mp3[i] == 1 ){if(s == -1){s = mp2[i];}else{t = mp2[i];}}}if(s > t) swap(s,t);//使小的為起點，大的為終點printf("%d",s);set<pair<int,int> >::iterator it,itt,temp,itt1;it = s1.lower_bound(make_pair(s,0));while(s1.size() > 2){itt = s1.lower_bound(make_pair(it->second,0));itt1 = s1.lower_bound(make_pair(it->second,it->first));s = itt->first;temp = it;if(s1.size() > 2){printf(" %d",s);}s1.erase(temp);s1.erase(itt1);it = s1.lower_bound(make_pair(s,0));}printf(" %d\n",t);}return 0; }

總結

以上是生活随笔為你收集整理的FZU Problem 2227 邮票的全部內容，希望文章能夠幫你解決所遇到的問題。

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