/* Main idea Find Euler Path, not circuit, so take care to choose a start node whose degree is odd; */ /* Executing... Test 1: TEST OK [0.000 secs, 3512 KB] Test 2: TEST OK [0.000 secs, 3512 KB] Test 3: TEST OK [0.000 secs, 3512 KB] Test 4: TEST OK [0.000 secs, 3512 KB] Test 5: TEST OK [0.000 secs, 3512 KB] Test 6: TEST OK [0.000 secs, 3512 KB] Test 7: TEST OK [0.011 secs, 3512 KB] Test 8: TEST OK [0.022 secs, 3512 KB] All tests OK. */ /* ID: haolink1 PROG: fence LANG: C++ */ //#include <iostream> #include <fstream> #include <list> using namespace std; const int MAX = 500; list<int> edges [MAX]; int path[1025]; int path_pos = 0; bool CompareValue(int e1, int e2){ return e1 <= e2 ? true : false; } void FindPath(int cur_node){ if(edges[cur_node].empty()){ path[path_pos] = cur_node; path_pos++; }else{ while(!edges[cur_node].empty()){ int neighbor = edges[cur_node].front(); //delete the edge to neighbor; edges[cur_node].pop_front(); for(list<int>::iterator it = edges[neighbor].begin(); it != edges[neighbor].end(); it++){ if(*(it) == cur_node){ edges[neighbor].erase(it); break; } } FindPath(neighbor); } path[path_pos] = cur_node; path_pos++; } } void FindEulerPath(){ path_pos = 0; //Choose the node whose degree is odd as start point; for(int i = 0; i < MAX; i++){ if(edges[i].size()%2 == 1){ FindPath(i); return; } } //If All nodes‘ degree is even, then choose the smallest num; for(int i = 0; i < MAX; i++){ if(!edges[i].empty()){ FindPath(i); return; } } } int main(){ int F = 0; ifstream fin("fence.in"); ofstream cout("fence.out"); fin >> F; for(int i = 0; i < F; i++){ int u = 0, v = 0; fin >> u >> v; u--; v--; edges[u].push_back(v); edges[v].push_back(u); } for(int i = 0; i < MAX; i++){ if(!edges[i].empty()){ edges[i].sort(CompareValue); } } FindEulerPath(); for(int i = F; i >= 0; i--){ cout << path[i]+1 << endl; } return 0; }
USACO 3.3 Riding The Fences (fence),布布扣,bubuko.com
USACO 3.3 Riding The Fences (fence)
原文:http://blog.csdn.net/damonhao/article/details/20132117