2404.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 2404 on 2006-10-26 at 21:37:54 */
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 10240;
const int INF = 1 << 20;

class Edge {
public:
	int u, cfr, cto;
	Edge(int cu, int cf, int ct) : u(cu), cfr(cf), cto(ct) {}
};

vector<Edge> g[N];
int b, e, path[N], pn;

bool dfs(int);

int main()
{
	int T;

	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		int n; scanf("%d", &n);
		for(int i = 0; i < n; i++) g[i].clear();
		for(int i = 1; i < n; i++) {
			int u, v, c1, c2; scanf("%d %d %d %d", &u, &v, &c1, &c2); u--; v--;
			g[u].push_back(Edge(v, c1, c2)); g[v].push_back(Edge(u, c2, c1));
		}
		scanf("%d %d", &b, &e); b--; e--;
		pn = 0; dfs(b);
		int mc = g[b][0].cfr, mi = g[b][0].cfr;
		for(int i = 1; i < pn-1; i++) {
			int v = path[i], ifr, ofr, ito, oto, sum = 0;
			for(int j = g[v].size()-1; j >= 0; j--) {
				if(g[v][j].u == path[i-1]) { ifr = g[v][j].cto; ito = g[v][j].cfr; }
				else if(g[v][j].u == path[i+1]) { ofr = g[v][j].cto; oto = g[v][j].cfr; }
				sum += g[v][j].cto;
			}
			mc <?= min(ifr, oto);
			for(int j = g[v].size()-1; j >= 0; j--)
				if(g[v][j].u != path[i-1] && g[v][j].u != path[i+1])
					mc <?= sum-g[v][j].cfr-g[v][j].cto;
			int minp = max(ifr+max(ito-ofr, 0)-sum+ofr+oto, 0);
			mi <?= max(minp+mi-ifr, 0);
		}
		printf("%d %d\n", mi, mc);
	}
	
	return 0;
}

bool dfs(int v)
{
	path[pn++] = v;
	if(v == e) return true;
	for(int i = g[v].size()-1; i >= 0; i--) {
		int u = g[v][i].u;
		if(pn != 1 && u == path[pn-2]) continue;
		else if(dfs(u)) return true;
	}
	pn--; return false;
}