打卡信奥刷题（2605）用C++实现信奥题 P2458 [SDOI2006] 保安站岗-开发者社区

P2458 [SDOI2006] 保安站岗

题目描述

五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。

已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需的费用不同。

一个保安一旦站在某个通道的其中一个端点，那么他除了能看守住他所站的那个端点，也能看到这个通道的另一个端点，所以一个保安可能同时能看守住多个端点（树的结点），因此没有必要在每个通道的端点都安排保安。

编程任务：

请你帮助超市经理策划安排，在能看守全部通道端点的前提下，使得花费的经费最少。

输入格式

第1 11行n nn，表示树中结点的数目。

第2 22行至第n + 1 n+1n+1行，每行描述每个通道端点的信息，依次为：该结点标号i ii（0 < i ≤ n 0<i \le n0<i≤n），在该结点安置保安所需的经费k kk（1 ≤ k ≤ 10000 1\le k \le 100001≤k≤10000），该边的儿子数m mm，接下来m mm个数，分别是这个节点的m mm个儿子的标号r 1 , r 2 , ⋯ , r m r_1,r_2,\cdots, r_mr1,r2,⋯,rm。

对于一个n nn（0 < n ≤ 1500 0<n \le 15000<n≤1500）个结点的树，结点标号在1 11到n nn之间，且标号不重复。

输出格式

输出一行一个整数，表示最少的经费。

输入输出样例 #1

输入 #1

6 1 30 3 2 3 4 2 16 2 5 6 3 5 0 4 4 0 5 11 0 6 5 0

输出 #1

说明/提示

样例解释

在结点2 , 3 , 4 2,3,42,3,4安置3 33个保安能看守所有的6 66个结点，需要的经费最小：25 2525。

C++实现

#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constint_=10005;constintINF=1e9;structedge{intto,next;}a[_<<1];intn,head[_],cnt,val[_],dp[3][_];intgi(){intx=0,w=1;charch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')w=-1,ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();returnx*w;}voidLink(intu,intv){a[++cnt]=(edge){v,head[u]};head[u]=cnt;}voiddfs(intu,intfa){intsum=0;dp[2][u]=val[u];for(inte=head[u];e;e=a[e].next){intv=a[e].to;if(v==fa)continue;dfs(v,u);sum+=min(dp[1][v],dp[2][v]);dp[2][u]+=min(min(dp[0][v],dp[1][v]),dp[2][v]);}dp[0][u]=sum;dp[1][u]=INF;for(inte=head[u];e;e=a[e].next){intv=a[e].to;if(v==fa)continue;dp[1][u]=min(dp[1][u],sum-min(dp[1][v],dp[2][v])+dp[2][v]);}}intmain(){n=gi();for(inti=1,k,u,v;i<=n;i++){u=gi();val[u]=gi();k=gi();for(intj=1;j<=k;j++)v=gi(),Link(u,v),Link(v,u);}dfs(1,0);printf("%d\n",min(dp[1][1],dp[2][1]));return0;}