【bzoj1917】[Ctsc2010]星际旅行

65 阅读 0 评论 43 点赞

我是靠谱客的博主冷艳外套，最近开发中收集的这篇文章主要介绍【bzoj1917】[Ctsc2010]星际旅行，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

公元3000年，地球联盟已经攻占了银河系内的N个星球，出于资金的考虑，政府仅仅在星球间建立了N-1条双向时空隧道保证任意两个星球之间互相可达。出于管理上的考虑，第i个星球的行政长官要求每个公民在一年内不得从该星球利用时空隧道次数超过Hi次（这一统计是基于离开次数统计的，如果你已经使用从该星球离开过Hi次，那么这一年内你就不能再使用时空隧道离开这个星球了）。Louis Paosen是一个星际旅行家，他希望能使用尽量多次的时空隧道，但又不希望最终被迫定居的星球条件太过恶劣。所以他希望能知道对于每个星球i，若从0号星球出发，最终以i号星球为终点，这样的星际旅行途中最多可以使用多少次时空隧道。

Input

第一行包含一个整数N。接下来的一行包含N个整数Hi，分别表示每个星球的离开次数限制。接下来N-1行每行两个整数，表示这两个星球之间有时空隧道连接。星球的编号从0开始，Louis Paosen一开始在0号星球。

Output

包含N行，每行一个整数，表示如果最终旅行结束在这个星球，最多可以使用时空隧道的次数。

Sample Input

3
2 6 2
0 1
1 2

Sample Output

8
7
8

HINT

40%的数据N≤500
100%的数据中N≤50000。
所有星球的离开次数限制满足1≤Hi≤40000，且每个星球的Hi大于等于与该星球直接相连的星球数（即度数）。

Source

Day1

【解析】

高级的树形dp解决树上网络流……

如果把限制看做流量上界，那么答案相当于从根节点1到树上所有点的最大流

剩下的看代码注释吧

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
	int x,y,next;
}a[110000];int len,last[51000];
int f,g[51000],c[51000];
void ins(int x,int y)
{
	len++;
	a[len].x=x;a[len].y=y;
	a[len].next=last[x];last[x]=len;
}
void dfs(int x,int fa)
{
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa)
		{
			dfs(y,x);
			int sum=min(c[x],c[y]);//记录最小的离开次数
			c[x]-=sum;c[y]-=sum;//减去离开的次数
			f+=sum*2;//两个点来回走,使用次数是2倍
			
			if(c[y]>0) g[x]=y;//x的儿子y还有离开的次数
		}
	}
}
int ans[51000],biaoji[51000];
void solve(int x,int fa)
{
	ans[x]=f;
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa)
		{
			//当前x的流量>0,那么可以直接走到y,使得y答案加1
			if(c[x]>0){c[x]--;f++;biaoji[x]=0;}
			//y的某个儿子u的流量>0,那可以把y->x的流量退掉,换成y->u,u->y使答案加1
			else if(g[y]>0){c[g[y]]--;f++;biaoji[x]=1;}
			//若上述情况都不存在,那y->x这条边流量必须退掉,因为到达x之后就返回不y了
			else {c[y]++;f--;biaoji[x]=2;}
			
			solve(y,x);
			
			if(biaoji[x]==0){c[x]++;f--;}
			else if(biaoji[x]==1){c[g[y]]++;f--;}
			else{c[y]--;f++;}
		}
	}
}
int main()
{
	int n,x,y;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&c[i]);
	len=0;memset(last,0,sizeof(last));
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);x++;y++;
		ins(x,y);ins(y,x);
		c[x]--;c[y]--;
		//因为每个星球的Hi大于等于与该星球直接相连的星球数,所以至少可以遍历所有的边一个来回
	}
	f=(n-1)*2;
	dfs(1,0);solve(1,0);
	for(int i=1;i<=n;i++) printf("%dn",ans[i]);
	return 0;
}