C++14(g++5.4) 解法, 执行用时: 723ms, 内存消耗: 1480K, 提交时间: 2019-11-22 23:55:48

#include <bits/stdc++.h>
using namespace std;

#define ff	first
#define ss	second

typedef pair<int, int> pii;

template<typename T> T& maxx(T& x, const T& y) { return x = max(x, y); }

constexpr const int maxn = 512;
constexpr const int maxw = 128;
int a[maxn], W;
double dp[maxn][maxw][2], tmp[maxw][2], P;
vector<pair<int, pii>> adj[maxn];

bool dfs(int u, int p) {
	dp[u][0][0] = dp[u][0][1] = 0;
	for (int w = 1; w <= W; ++w) dp[u][w][0] = dp[u][w][1] = -1e10;
	for (const auto& e : adj[u]) {
		int v = e.ff;
		if (v == p) continue;
		if (dfs(v, u)) return true;
		for (int w = 0; w <= W; ++w) tmp[w][0] = tmp[w][1] = -1e10;
		for (int w = 0; w <= W; ++w) for (int _w = 0; _w <= W; ++_w) {
			maxx(tmp[min(W, w + _w)][0], dp[u][w][0] + dp[v][_w][1]);
			maxx(tmp[min(W, w + _w)][1], dp[u][w][1] + dp[v][_w][1]);
			maxx(tmp[min(W, w + _w + e.ss.ss)][1], dp[u][w][0] + dp[v][_w][0] + e.ss.ff - e.ss.ss * P);
		}
		for (int w = 0; w <= W; ++w) {
			dp[u][w][0] = tmp[w][0];
			dp[u][w][1] = max(tmp[w][0], tmp[w][1]);
		}
		if (dp[u][W][1] >= 0) return true;
	}
	return false;
}

int main() {
	int n;
	cin >> n >> W;
	for (int u = 1; u <= n; ++u) cin >> a[u];
	for (int i = 1; i != n; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].emplace_back(v, pii(a[u] + a[v], w));
		adj[v].emplace_back(u, pii(a[u] + a[v], w));
	}
	double l = 0, r = 2e6;
	while (r - l > 1e-3) {
		P = (l + r) / 2;
		(dfs(1, 0) ? l : r) = P;
	}
	cout << fixed << setprecision(2) << (l + r) / 2 << endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 1388ms, 内存消耗: 1248K, 提交时间: 2019-11-22 21:33:09

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,a[505];
vector<pair<int,int> >E[505];
double f[2][505][105],g[2][105];
void cmax(double &x,double y){
	x=max(x,y);
}
void dfs(int u,int fa,double mid){
	for(int i=1;i<=m;++i)f[0][u][i]=f[1][u][i]=-1e20;
	f[0][u][0]=f[1][u][0]=0;
	for(auto x:E[u]){
		int v=x.first,w=x.second;
		if(v!=fa){
			dfs(v,u,mid);
			double t=a[u]+a[v]-mid*w;
			for(int i=0;i<=m;++i)g[0][i]=g[1][i]=-1e20;
			for(int i=m;~i;--i)
				for(int j=m;~j;--j){
					cmax(g[1][min(i+j,m)],f[1][u][i]+f[1][v][j]);
					cmax(g[1][min(i+j+w,m)],f[0][u][i]+f[0][v][j]+t);
					cmax(g[0][min(i+j,m)],f[0][u][i]+f[1][v][j]);
				}
			for(int i=0;i<=m;++i)
				f[0][u][i]=g[0][i],f[1][u][i]=g[1][i];
		}
	}
	for(int i=0;i<=m;++i)cmax(f[1][u][i],f[0][u][i]);
	/*
	printf("u=%d\n",u);
	for(int i=0;i<=m;++i){
		if(f[0][u][i]>-1e20)
			printf("f[0][u][%d]=%.2lf\n",i,f[0][u][i]);
		if(f[1][u][i]>-1e20)
			printf("f[1][u][%d]=%.2lf\n",i,f[1][u][i]);
	}
	*/
}
int main(){
//	freopen("test.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1,x,y,z;i<n;++i){
		scanf("%d%d%d",&x,&y,&z);
		E[x].push_back({y,z});
		E[y].push_back({x,z});
	}
	double l=0,r=2e6;
	while(l+1e-3<r){
		double mid=(l+r)/2;
//		mid=2.44;
		dfs(1,0,mid);
		if(f[1][1][m]>0)l=mid;
		else r=mid;
//		return 0;
	}
	printf("%.2lf\n",l);
	return 0;
}