题目链接

题意分析

一看就知道是一道\(01\)分数规划的题
我们二分值之后跑树形背包就可以了
CODE:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<cstdlib>

#include<string>

#include<queue>

#include<map>

#include<stack>

#include<list>

#include<set>

#include<deque>

#include<vector>

#include<ctime>

#define ll long long

#define inf 1e9

#define N 508

#define IL inline

#define M 1008611

#define D double

#define eps 1e-5

#define R register

using namespace std;

template<typename T>IL void read(T &_)

{

    T __=0,___=1;char ____=getchar();

    while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}

    while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}

    _=___ ? __:-__;

}

/*-------------OI使我快乐-------------*/

int n,m,tot;

struct Node

{

	int xx,yy;

}e[N];

D dp[N][N],num[N];

D le,ri=inf,ans;

int siz[N],to[N],nex[N],head[N];

IL void add(int x,int y)

{to[++tot]=y;nex[tot]=head[x];head[x]=tot;}

IL void dfs(int now,int fat)

{

	dp[now][0]=0;siz[now]=1;

	for(R int i=head[now];i;i=nex[i])

	{

		int v=to[i];

		if(v==fat) continue;

		dfs(v,now);

		siz[now]+=siz[v];

		for(R int j=min(m,siz[now]);j>=0;--j)

		 for(R int k=0;k<=min(j,siz[v]);++k)

		  dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[v][k]);

	}

	for(R int i=siz[now];i;--i) dp[now][i]=dp[now][i-1]+num[now];

}

IL bool check(D now)

{

	for(R int i=1;i<=n;++i)

	 for(R int j=0;j<=m;++j) dp[i][j]=-inf;

	for(R int i=1;i<=n;++i) num[i]=(D)e[i].xx-((D)now*e[i].yy);

	dfs(1,0);

	for(R int i=1;i<=n;++i)

	if(dp[i][m]>-eps) return 1;

	return 0;

}

int main()

{

//	freopen(".in","r",stdin);

//	freopen(".out","w",stdout);

	read(n);read(m);m=n-m;

	for(R int i=1;i<=n;++i) read(e[i].xx);

	for(R int i=1;i<=n;++i) read(e[i].yy);

	for(R int i=1,x,y;i<n;++i)

	{

		read(x);read(y);

		add(x,y);add(y,x);

	}

	while((ri-le)>eps)

	{

		D mid=(le+ri)/2.0;

		if(check(mid)) ans=le=mid;

		else ri=mid;

	}

	printf("%.1f\n",ans);

//	fclose(stdin);

//	fclose(stdout);

    return 0;

}
巴特西

P1642 规划

题目链接

题意分析

CODE:

HEOI 2019 RP++

最新文章

热门文章
