2374.cpp

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

/* This Code is Submitted by wywcgs for Problem 2374 on 2006-09-27 at 14:32:22 */
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int V = 10240;

int cnt, dfn[V];
vector<pii> g[V];

void dfs(int);

int main()
{
	int n, v, plen[V][2], len[V][2];
	double best;
	
	while(scanf("%d %d", &v, &n) != EOF && v != 0) {
		for(int i = 0; i < v; i++) g[i].clear();
		for(int i = 1; i < v; i++) {
			int a, b, w; scanf("%d %d %d", &a, &b, &w);
			g[a].push_back(pii(b, w)); g[b].push_back(pii(a, w));
		}
		cnt = 0; memset(dfn, -1, sizeof(dfn)); dfs(0);
		memset(len, -1, sizeof(len)); memset(plen, 0, sizeof(plen)); best = -1e20;
		int lmt = min(v-1, 2*n-1);
		for(int tn = 1; tn <= lmt; tn++) {
			int nlen[V][2], nplen[V][2], pn = -1;
			memset(nlen, -1, sizeof(nlen)); memset(nplen, -1, sizeof(nplen));
			for(int i = 0; i < v; i++)
				for(int j = g[i].size()-1; j >= 0; j--) {
					int u = g[i][j].first, tl, tmp = g[i][j].second;
					if(dfn[i] < dfn[u]) tl = plen[u][1];
					else tl = plen[i][0];
					if(tl == len[u][0]) tl = len[u][1];
					else tl >?= len[u][0];
					if(tl < 0) continue;
					tmp += tl;
					if(dfn[i] < dfn[u]) nplen[u][0] = tmp;
					else nplen[i][1] = tmp;
					for(int k = 0; k < 2; k++)
						if(tmp > nlen[i][k]) swap(tmp, nlen[i][k]);
				}
			if(!memcmp(len, nlen, sizeof(nlen))) break;
			memcpy(len, nlen, sizeof(nlen)); memcpy(plen, nplen, sizeof(nplen));
			if(tn < n) continue;
			for(int i = 0; i < v; i++) pn >?= len[i][0];
			if(pn < 0) break;
			best >?= 1.0*pn/tn;
		}
		if(best < 0) printf("N/A\n");
		else printf("%.2lf\n", best);
	}
	
	return 0;
}

void dfs(int u)
{
	if(dfn[u] != -1) return;
	dfn[u] = cnt++;
	for(int i = g[u].size()-1; i >= 0; i--) dfs(g[u][i].first);
}