朵以服饰 网站建设建设工程施工合同2017

朵以服饰 网站建设,建设工程施工合同2017,wordpress win8模板,wordpress php配置P2458 [SDOI2006] 保安站岗 题目描述 五一来临#xff0c;某地下超市为了便于疏通和指挥密集的人员和车辆#xff0c;以免造成超市内的混乱和拥挤#xff0c;准备临时从外单位调用部分保安来维持交通秩序。 已知整个地下超市的所有通道呈一棵树的形状#xff1b;某些通道…P2458 [SDOI2006] 保安站岗题目描述五一来临某地下超市为了便于疏通和指挥密集的人员和车辆以免造成超市内的混乱和拥挤准备临时从外单位调用部分保安来维持交通秩序。已知整个地下超市的所有通道呈一棵树的形状某些通道之间可以互相望见。总经理要求所有通道的每个端点树的顶点都要有人全天候看守在不同的通道端点安排保安所需的费用不同。一个保安一旦站在某个通道的其中一个端点那么他除了能看守住他所站的那个端点也能看到这个通道的另一个端点所以一个保安可能同时能看守住多个端点树的结点因此没有必要在每个通道的端点都安排保安。编程任务请你帮助超市经理策划安排在能看守全部通道端点的前提下使得花费的经费最少。输入格式第1 11行n nn表示树中结点的数目。第2 22行至第n 1 n1n1行每行描述每个通道端点的信息依次为该结点标号i ii0 i ≤ n 0i \le n0i≤n在该结点安置保安所需的经费k kk1 ≤ 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 nn0 n ≤ 1500 0n \le 15000n≤1500个结点的树结点标号在1 11到n nn之间且标号不重复。输出格式输出一行一个整数表示最少的经费。输入输出样例 #1输入 #16 1 30 3 2 3 4 2 16 2 5 6 3 5 0 4 4 0 5 11 0 6 5 0输出 #125说明/提示样例解释在结点2 , 3 , 4 2,3,42,3,4安置3 33个保安能看守所有的6 66个结点需要的经费最小25 2525。C实现#includecstdio#includecstring#includealgorithmusingnamespacestd;constint_10005;constintINF1e9;structedge{intto,next;}a[_1];intn,head[_],cnt,val[_],dp[3][_];intgi(){intx0,w1;charchgetchar();while((ch0||ch9)ch!-)chgetchar();if(ch-)w-1,chgetchar();while(ch0ch9)x(x3)(x1)ch-0,chgetchar();returnx*w;}voidLink(intu,intv){a[cnt](edge){v,head[u]};head[u]cnt;}voiddfs(intu,intfa){intsum0;dp[2][u]val[u];for(intehead[u];e;ea[e].next){intva[e].to;if(vfa)continue;dfs(v,u);summin(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(intehead[u];e;ea[e].next){intva[e].to;if(vfa)continue;dp[1][u]min(dp[1][u],sum-min(dp[1][v],dp[2][v])dp[2][v]);}}intmain(){ngi();for(inti1,k,u,v;in;i){ugi();val[u]gi();kgi();for(intj1;jk;j)vgi(),Link(u,v),Link(v,u);}dfs(1,0);printf(%d\n,min(dp[1][1],dp[2][1]));return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容