2132.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2132 on 2006-03-01 at 21:02:08 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int MAX = 1024;
const int INF = 1 << 30;

class Graph {
private:
	vector<pii> next[2][MAX];
	int in[2][MAX], d[2][MAX], prev[2][MAX], path[2*MAX], pn;
	void go(int, int);
public:
	int n;
	void make(int, int);
	void ski();
};
void Graph::go(int src, int o) {
	int i, stack[MAX], sn = 0, inx[MAX];
	memcpy(inx, in[o], sizeof(in[o]));
	for(i = 0; i < n; i++) d[o][i] = (o == 0) ? -INF : INF;
	d[o][src] = 0; prev[o][src] = -1;
	for(i = 0; i < n; i++) 
		if(inx[i] == 0) stack[sn++] = i;
	while(sn > 0) {
		int p = stack[--sn];
		for(i = 0; i < (int)next[o][p].size(); i++) {
			int k = next[o][p][i].first, m = next[o][p][i].second;
			if((o == 0 && d[o][p]+m > d[o][k]) || (o == 1 && d[o][p]+m < d[o][k])) 
				{ d[o][k] = d[o][p]+m; prev[o][k] = p; }
			if(--inx[k] == 0) stack[sn++] = k;
		}
	}
}
void Graph::make(int m, int k) {
	int i, j;
	memset(in, 0, sizeof(in));
	for(i = 0; i < 2; i++)
		for(j = 0; j < n; j++) next[i][j].clear();
	for(i = 0; i < m+k; i++) {
		int a, b, d;
		scanf("%d %d %d", &a, &b, &d); a--; b--;
		if(i < m) { next[0][b].push_back(pii(a, d)); in[0][a]++; }
		else { next[1][a].push_back(pii(b, d)); in[1][b]++; }
	}
}
void Graph::ski() {
	int i, j, v, temp[MAX], stack[MAX], sn = 0;
	int inx[2][MAX]; memcpy(inx, in, sizeof(in));
	double best = -INF;
	for(i = 0; i < n; i++) 
		if(inx[0][i]+inx[1][i] == 0) stack[sn++] = i;
	while(sn > 0) {
		int p = stack[--sn];
		go(p, 0); go(p, 1);
		for(i = 0; i < n; i++) {
			if(d[0][i] == -INF || d[1][i] == INF) continue;
			double scary = 1.0 * d[0][i] / d[1][i];
			if(best < scary) {
				best = scary; int k = pn = 0;
				for(v = i; v != -1; v = prev[1][v]) temp[k++] = v;
				while(k > 0) path[pn++] = temp[--k];
				for(v = prev[0][i]; v != -1; v = prev[0][v]) path[pn++] = v;
			}
		}
		for(i = 0; i < 2; i++)
			for(j = 0; j < (int)next[i][p].size(); j++) {
				int o = next[i][p][j].first;
				if((--inx[i][o])+inx[1-i][o] == 0) stack[sn++] = o;
			}
	}
	for(i = 0; i < pn; i++) printf("%d ", path[i]+1);
	printf("\n%.3lf\n", best);
}

int main()
{
	Graph g;
	int t, T, m, k;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d %d", &g.n, &m, &k);
		g.make(m, k); g.ski();
	}
	
	return 0;
}