ZROI #365. 【2018普转提day18专题】嘤嘤嘤嘤

直接放代码

具体做法见注释

#include<stdio.h>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<cmath>

#include<iostream>

#include<queue>

#include<string>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef long double ld;

typedef unsigned long long ull;

typedef pair<long long,long long> pll;

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define rep(i,j,k)  for(register int i=(int)(j);i<=(int)(k);i++)

#define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)

ll read(){

	ll x=0,f=1;char c=getchar();

	while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}

	return x*f;

}

const int maxn=5050,maxm=1000100;

int n,m,T;

int ok[maxm],v[maxn],rk[maxm],tv[maxn];

double ans,base,f[maxn][2];

int head[maxn],to[maxn*2],nxt[maxn*2],tot;

void addedge(int x,int y){

	to[++tot]=y;nxt[tot]=head[x];head[x]=tot;

	to[++tot]=x;nxt[tot]=head[y];head[y]=tot;

}

//f[u][0]表示以u为根的子树内部最大收益

//f[u][1]表示以u为根的子树内部并且有一条链以u为一个端点的最大收益

void dfs(int u,int pa){

	f[u][0]=0;f[u][1]=tv[u]-base;

	double nw=0;

	for(int i=head[u];i;i=nxt[i]){

		int v=to[i];

		if(v==pa) continue;

		dfs(v,u);

		f[u][0]=max(f[u][0]+f[v][0],f[u][1]+f[v][1]+base);

		//后一个表示u连向v，并且因为上面减了一次base，v里面减了一次 所以我们得加回来

		//这时候经过u的链对于u而言有两条出边

		f[u][1]=max(f[u][1]+f[v][0],nw+f[v][1]+tv[u]);

		//后一个表示u连向v的收益，即v前面的儿子全都不连向u

		//这时候经过u的链对于u而言有一条出边

		nw+=f[v][0];

	}

	f[u][0]=max(nw,max(f[u][0],f[u][1]));

}

bool pd(double x){

	base=x;dfs(1,0);

	return f[1][0]>=x;

}

int main(){

	n=read(),m=read();

	rep(i,1,n) v[i]=read(),ok[m-v[i]-1]=1;

	rep(i,1,n-1){

		int x=read(),y=read();

		addedge(x,y);

	}

	T=read();ok[T]=1;

	rep(i,0,T) rk[i]=i;

	random_shuffle(rk,rk+1+T);

	rep(i,0,T){

		int &nw=rk[i];

		if(!ok[nw]) continue;

		rep(k,1,n){

			tv[k]=v[k]+nw;

			if(tv[k]>=m) tv[k]-=m;

		}

		if(!pd(ans)) continue;

		double l=ans,r=n*m*1.0/2;

		while(r-l>1e-7){

			double md=(l+r)/2;

			if(pd(md)) l=md,ans=md; else r=md;

		}

	}

	printf("%.7lf\n",ans);

	return 0;

}

Review

为什么这么想？

首先是二分答案分数规划，这很显然

关键在于把\(\frac {S} {K+1} \ge Ans\)变成\(S-K \cdot Ans \ge Ans\)

然后就是每选一条链的代价为Ans，并且最终收益大于等于Ans

这样就可以树形dp了

巴特西

ZROI #365. 【2018普转提day18专题】嘤嘤嘤嘤

ZROI #365. 【2018普转提day18专题】嘤嘤嘤嘤

Review

最新文章

热门文章