[CTSC2010]星际旅行

系统管理员 2021-09-29 21:52 278阅读 0赞

[https://www.luogu.org/problemnew/show/P4189][https_www.luogu.org_problemnew_show_P4189]

#### 题解 ####

模拟费用流。

首先有一个非常好的条件，每个点的限制次数都大于等于这个点的度数。

然后我们可以从\\(0\\)开始\\(dfs\\)一遍这棵树。

然后如果一条边连接的两个点的\\(h\\)同时\\(>0\\)，那么就来回走。

然后我们考虑再去从\\(0\\)号节点往每个节点走。

如果此时\\(u\\)的\\(h>0\\)，那么直接走就可以了。

如果不是这样，那么我们为了从\\(u\\)走到\\(v\\)，必须将上一次\\(uv\\)折返的路程去掉，这样会使\\(v\\)的次数\\(+1\\)，这时如果\\(v\\)的一个儿子的次数不为\\(0\\)，那么还可以继续折返一次。

#### 代码 ####

#include<bits/stdc++.h> #define N 50009 using namespace std; typedef long long ll; int head[N],tot,h[N],ans[N],now,p[N],n; inline ll rd(){ ll x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } struct edge{ int n,to; }e[N<<1]; inline void add(int u,int v){ e[++tot].n=head[u];e[tot].to=v;head[u]=tot; } void dfs(int u,int fa){ for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){ int v=e[i].to; dfs(v,u); int x=min(h[u],h[v]); now+=x*2; h[u]-=x;h[v]-=x; if(h[v])p[u]=v; } } void dfs2(int u,int fa){ ans[u]=now; for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){ int v=e[i].to; if(h[u]){ h[u]--;now++; dfs2(v,u); h[u]++;now--; } else if(p[v]){ h[p[v]]--;now++; dfs2(v,u); h[p[v]]++;now--; } else{ h[v]++;now--; dfs2(v,u); h[p[v]]--;now++; } } } int main(){ n=rd();int u,v; for(int i=1;i<=n;++i)h[i]=rd(); for(int i=1;i<n;++i){ u=rd()+1;v=rd()+1; add(u,v);add(v,u); h[u]--;h[v]--;now+=2; } dfs(1,0); dfs2(1,0); for(int i=1;i<=n;++i)printf("%d\n",ans[i]); return 0; }

转载于:https://www.cnblogs.com/ZH-comld/p/10794064.html

[https_www.luogu.org_problemnew_show_P4189]: https://www.luogu.org/problemnew/show/P4189

发表评论取消回复

表情：

评论列表（有 0 条评论，278人围观）

还没有评论，来说两句吧...

相关阅读

相关 [CTSC2017]密钥

[题目][Link 1] 一个显然的暴力就是枚举\\(\\rm X\\)的位置，把\\(\\rm A\\)视为\\(1\\)，\\(\\rm B\\)视为\\(-1\\)，从

红太狼/ 2023年10月11日 04:49/ 0 赞/ 25 阅读

相关编程题：星际穿越

题目描述航天飞行器是一项复杂而又精密的仪器，飞行器的损耗主要集中在发射和降落的过程，科学家根据实验数据估计，如果在发射过程中，产生了 x 程度的损耗，那么在降落的过程中

短命女/ 2022年05月23日 05:12/ 0 赞/ 216 阅读

相关 [Ctsc2015]misc

[https://lydsy.com/JudgeOnline/problem.php?id=4055][https_lydsy.com_JudgeOnline_problem.

蔚落/ 2022年01月06日 15:59/ 0 赞/ 245 阅读

相关 [CTSC2017]网络

[\[CTSC2017\]网络][CTSC2017] 连一条长度为len的边，使得基环树的直径最小结论：一定连在某条直径两个点上（否则更靠近不劣）然后二分答案判定。

清疚/ 2021年12月23日 15:09/ 0 赞/ 168 阅读

相关【loj2263】【CTSC2017】游戏

题目小\\(R\\)和小\\(B\\)一共完了\\(n\\)局游戏，第一局小\\(R\\)获胜的概率为\\(p\_i\\)，没有平局，对于第$ i $局游戏： 1.

╰半橙微兮°/ 2021年12月23日 01:41/ 0 赞/ 218 阅读

相关 P4218 [CTSC2010]珠宝商

P4218 \[CTSC2010\]珠宝商 -------------------- 神题... 可以想到点分治，细节不写了。。。（学了个新姿势，sam可以在前面

「爱情、让人受尽委屈。」/ 2021年12月09日 00:39/ 0 赞/ 213 阅读

相关 7.18 T1 星际旅行

题意：n个点，m条边，无重边，有自环，要求经过m-2条边两次，2条边一次，问共有多少种本质不同的方案。本质不同：当且仅当至少存在一条边经过次数不同。题解：考试的时候理解错题

小鱼儿/ 2021年11月27日 01:02/ 0 赞/ 263 阅读

相关 HZOJ 星际旅行

正解欧拉路，其实看完题解还是挺简单的，由于对欧拉路这种东西没怎么接触过，所以考试时没想出来，知识还是有漏洞啊。另外这题的题解写的也不是很清楚（可能大佬作者觉得这是一道送分题

傷城~/ 2021年11月09日 09:12/ 0 赞/ 374 阅读

相关 [CTSC1997]选课

[题面][Link 1] 题解树形背包板子题。设\\(f\[i\]\[j\]\\)表示在以\\(x\\)为根的子树选\\(j\\)门课（包括\\(x\\)）能

柔情只为你懂/ 2021年10月23日 14:36/ 0 赞/ 322 阅读

相关 [CTSC2010]星际旅行

[https://www.luogu.org/problemnew/show/P4189][https_www.luogu.org_problemnew_show_P4189]

系统管理员/ 2021年09月29日 21:52/ 0 赞/ 279 阅读