打卡信奥刷题（3504）用C++实现信奥题 P10838 『FLA - I』庭中有奇树

P10838 『FLA - I』庭中有奇树题目背景某天晚上小 G 和小 Y 本打算激情 CF 但过掉两题就下班了然后他们准备玩一个游戏。题目描述给定一棵有nnn个节点的无根树边带权树上有一个起始节点SSS和一个终止节点TTT。有一枚可以沿着边在节点之间移动的棋子它每次移动花费的硬币数量等于经过的边的权值。如果当前棋子所在节点为uuu且节点vvv与节点uuu之间连有一条权值为www的边小 G 就能花费www个硬币把棋子移动到节点vvv。游戏开始时棋子位于节点SSS我们的小 G 要控制棋子移动到节点TTT。由于曾经有人告诉小 G 玩某游戏不开挂等于没玩小 G 决定开挂。他的外挂可以花费kkk个硬币把棋子从当前节点传送到任意一个没有和当前节点连边的节点小 G 只能用这个外挂至多一次。正义的小 Y 不能坐视不管在小 G 开始行动之前小 Y 可以封锁至多mmm条可能的传送路线。假设小 Y 封锁了从节点xxx向节点yyy的传送路线小 G 把棋子从节点xxx传送到节点yyy花费的硬币数量就会变成10910^9109。由于外挂功能强大小 G 知道小 Y 都封锁了哪些路线。请注意传送路线是单向的封锁节点xxx向节点yyy的传送路线不影响小 G 从节点yyy向节点xxx传送。有趣的是游戏中小 G 不仅负责控制棋子移动到节点TTT还想最小化花费的硬币数量而小 Y 想要最大化小 G 花费的硬币数量。如果两人都采取最优策略小 G 总共会花掉多少硬币输入格式第一行输入五个整数n,m,k,S,Tn,m,k,S,Tn,m,k,S,T。接下来n−1n-1n−1行第iii行输入三个正整数ui,vi,wiu_i,v_i,w_iui​,vi​,wi​表示节点uiu_iui​和节点viv_ivi​之间有一条边权为wiw_iwi​的边。输出格式输出一行一个整数表示在两人都采取最优策略的情况下小 G 花费的硬币数量。输入输出样例 #1输入 #14 2 2 1 2 2 3 6 4 1 6 3 1 8输出 #114输入输出样例 #2输入 #29 7 4 1 6 3 8 7 6 8 6 6 7 4 2 5 3 3 2 2 3 9 12 2 1 2 8 4 11输出 #212说明/提示「样例解释 #1」给出一种可能发生的情况小 Y 封锁节点111向节点222的传送路线和节点444向节点222的传送路线。小 G 控制棋子从初始节点到达节点444从节点444传送到节点333后再到达终止节点总共花费141414个硬币。「数据范围」本题采用捆绑测试。Subtaskn≤n\leqn≤m≤m \leqm≤特殊性质分值#110001000100010510^5105无101010#210510^5105000无101010#310510^510510510^5105无101010#410510^510510910^9109A151515#510510^510510910^9109B151515#610510^510510910^9109无404040特殊性质 A保证k109k10^9k109。特殊性质 B保证k0k0k0。对于所有测试数据2≤n≤1052 \leq n \leq 10^52≤n≤1050≤m,k≤1090 \leq m,k \leq 10^90≤m,k≤1091≤S,T,ui,vi≤n1 \leq S,T,u_i,v_i \leq n1≤S,T,ui​,vi​≤n1≤wi≤1091 \leq w_i \leq 10^91≤wi​≤109S≠TS \neq TSTui≠viu_i \neq v_iui​vi​。节点的编号是从111到nnn的整数。C实现#includebits/stdc.h#definelllonglongusingnamespacestd;constll N1e55,cst1e9;structedge{ll v,w;};ll n,m,k,S,T,u,v,w;ll ds[N],dt[N],ss[N],tt[N];vectoredgeG[N];voiddfs(ll x,ll fa,ll sum,ll dis[]){dis[x]sum;for(edge e:G[x]){ll ye.v,ze.w;if(yfa)continue;dfs(y,x,sumz,dis);}}boolcheck(ll mid){ll sum0;for(ll i1;in;i)sumupper_bound(tt1,ttn1,mid-ss[i])-tt-1;for(ll i1;in;i){for(edge e:G[i]){ll je.v;if(ds[i]dt[j]mid)sum--;}}returnsumm;}intmain(){cinnmkST;for(ll i1;in;i){cinuvw;G[u].push_back({v,w});G[v].push_back({u,w});}dfs(S,0,0,ds);dfs(T,0,0,dt);for(ll i1;in;i)ss[i]ds[i],tt[i]dt[i];sort(ss1,ssn1);sort(tt1,ttn1);ll l0,r1e18,t1e18;while(lr){ll mid(lr)/2;if(check(mid))tmid,rmid-1;elselmid1;}coutmin(ds[T],min(tk,cst));return0;}2024 年 8 月 4 日将样例置于 Subtask #0。后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容