P10949 四叶草魔杖题目描述魔杖护法 Freda 融合了四件武器于是魔杖顶端缓缓地生出了一棵四叶草四片叶子幻发着淡淡的七色光。圣剑护法 rainbow 取出了一个圆盘圆盘上镶嵌着NNN颗宝石编号为0∼N−10 \sim N-10∼N−1。第iii颗宝石的能量是AiA_iAi。如果Ai0A_i 0Ai0表示这颗宝石能量过高需要把AiA_iAi的能量传给其它宝石如果Ai0A_i 0Ai0表示这颗宝石的能量过低需要从其它宝石处获取−Ai-A_i−Ai的能量。保证∑Ai0\sum A_i 0∑Ai0。只有当所有宝石的能量均相同时把四叶草魔杖插入圆盘中央才能开启超自然之界的通道。不过只有MMM对宝石之间可以互相传递能量其中第iii对宝石之间无论传递多少能量都要花费TiT_iTi的代价。探险队员们想知道最少需要花费多少代价才能使所有宝石的能量都相同输入格式第一行两个整数N,MN,MN,M。第二行NNN个整数AiA_iAi。接下来MMM行每行三个整数pi,qi,Tip_i,q_i,T_ipi,qi,Ti表示在编号为pip_ipi和qiq_iqi的宝石之间传递能量需要花费TiT_iTi的代价。数据保证每对pi,qip_i,q_ipi,qi最多出现一次。输出格式输出一个整数表示答案无解输出Impossible。输入输出样例 #1输入 #13 3 50 -20 -30 0 1 10 1 2 20 0 2 100输出 #130说明/提示2≤N≤162 \le N \le 162≤N≤16,0≤M≤N(N−1)20 \le M \le \dfrac{N(N-1)}{2}0≤M≤2N(N−1),0≤pi,qiN0 \le p_i,q_i N0≤pi,qiN,−1000≤Ai≤1000-1000 \le A_i \le 1000−1000≤Ai≤1000,0≤Ti≤10000 \le T_i \le 10000≤Ti≤1000C实现#includeiostream#includecstring#includealgorithm#defineregregisterusingnamespacestd;constintN17;intn,m,dp[1N],sum[1N],mst[1N],b[1N];structedge{intu,v,w;}e[300];intmain(){ios::sync_with_stdio(0);cinnm;regintx,y,z;for(inti0;in;i)cinsum[1i];for(inti0;im;i)cine[i].ue[i].ve[i].w;for(inti2;i1n;i)sum[i]sum[i^(i-i)]sum[i-i];memset(mst,0x3f,sizeofmst);mst[0]0;for(inti0;in;i)mst[1i]0;for(inti1;i1n;i)for(intj0;jm;j){xe[j].u;ye[j].v;ze[j].w;if(!(i(1x))||!(i(1y)))continue;mst[i]min({mst[i],mst[i^(1x)]z,mst[i^(1y)]z});}memset(dp,0x3f,sizeofdp);dp[0]0;for(reginti1;i1n;i){if(sum[i])continue;for(x0,yi;y;x,y^y-y)b[1x]y-y;for(regintj0;j1x;j){for(yj,z0;y;y^y-y)z|b[y-y];if(sum[z])continue;dp[i]min(dp[i],dp[z]mst[i^z]);}}if(dp[(1n)-1]0x3f3f3f3f)coutImpossible;elsecoutdp[(1n)-1];return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容