1045.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1045 on 2006-01-18 at 20:36:49 */ 
#include <cstdio>
#include <list>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 2048;
const int N_MAX = 64;

class Road {
public:
	int n1, n2;
	void make(int, int);
};
void Road::make(int x1, int x2) {
	n1 = x1; n2 = x2;
}

list<int> path[N_MAX][N_MAX];
int d[N_MAX], m, pn;
int rn[N_MAX][N_MAX];

void eulerPath(int);
bool bridge(int, int);

int main()
{
	Road road[MAX];
	int n, b, i, j;
	
	while(true) {
		memset(rn, 0, sizeof(rn)); memset(d, 0, sizeof(d));
		for(n = 0, m = 0; true; n++) {
			int x, y, o;
			scanf("%d %d", &x, &y);
			if(x == 0 && y == 0) break;
			else {
				if(n == 0) b = min(x, y);
				scanf("%d", &o);
				road[o].make(x, y);
				d[x]++; d[y]++; rn[x][y]++; rn[y][x]++;
				m = max(m, max(x, y));
			}
		}
		if(n == 0) break;
		else {
			bool can = true;
			for(i = 1; i <= m && can; i++)
				if(d[i] % 2 != 0) can = false;
			if(!can) printf("Round trip does not exist.");
			else {
				for(i = 0; i <= m; i++)
					for(j = 0; j <= m; j++) path[i][j].clear();
				for(i = 1; i <= n; i++) {
					path[road[i].n1][road[i].n2].push_back(i);
					path[road[i].n2][road[i].n1].push_back(i);
				}
				pn = 0;
				eulerPath(b);
			}
			putchar('\n');
		}
	}
	
	return 0;
}

void eulerPath(int b)
{
	int i;
	while(d[b] != 0) {
		int best = MAX, bo, bt = MAX, bot;
		for(i = 1; i <= m; i++)
			if(!path[i][b].empty() && best > path[i][b].front()) {
				if(bridge(b, i) && bt > path[i][b].front()) bt = path[i][b].front(), bot = i;
				else best = path[i][b].front(), bo = i;
			}
		if(best == MAX) best = bt, bo = bot;
		d[b]--; d[bo]--; rn[b][bo]--; rn[bo][b]--;
		path[bo][b].pop_front(); path[b][bo].pop_front();
		if(pn++ != 0) putchar(' ');
		printf("%d", best);
		eulerPath(bo);
	}
}
bool bridge(int x, int y)
{
	bool vst[N_MAX] = { false };
	rn[x][y]--; rn[y][x]--;
	queue<int> Q;
	Q.push(x); vst[x] = true;
	while(!Q.empty() && !vst[y]) {
		int p = Q.front(), i; Q.pop();
		for(i = 1; i <= m; i++)
			if(!vst[i] && rn[i][p] != 0) Q.push(i), vst[i] = true;
	}
	rn[x][y]++; rn[y][x]++;
	return !vst[y];
}