P6883 [COCI 2016/2017 #3] Kroničan题目描述Mislav 有N NN个玻璃杯从1 ∼ N 1\sim N1∼N编号每个玻璃杯中都有一定的水。你需要通过倒水将某个杯子中的水倒入另一个杯子使这些杯子中只有K KK个有水。已知将第i ii号玻璃杯中的水倒入第j jj号需要消耗C i , j C_{i,j}Ci,j​的代价。Mislav 想知道经过倒水后满足只有K KK个或更少玻璃杯中有水时消耗的代价总和的最小值。输入格式第一行包含两个正整数N , K N,KN,K。接下来N NN行每行包含N NN个非负整数C i , j C_{i,j}Ci,j​。第i ii行j jj列的数表示从玻璃杯i ii倒水到玻璃杯j jj需要付出的代价。保证C i , i C_{i,i}Ci,i​一定是0 00。输出格式输出 Mislav 达成目标需要付出的最小代价和。输入输出样例 #1输入 #13 3 0 1 1 1 0 1 1 1 0输出 #10输入输出样例 #2输入 #23 2 0 1 1 1 0 1 1 1 0输出 #21输入输出样例 #3输入 #35 2 0 5 4 3 2 7 0 4 4 4 3 3 0 1 2 4 3 1 0 5 4 5 5 5 0输出 #35说明/提示样例 1 解释Mislav 不需要倒水。代价和是0 00。样例 2 解释Mislav 需要将任意一个玻璃杯中的水倒入任何其他玻璃杯中使其满足只有两个玻璃杯中有水。代价和为1 11。样例 3 解释Mislav 可以将水从玻璃杯4 44倒入玻璃杯3 33然后将玻璃杯3 33中的水倒入玻璃杯5 55最后将玻璃杯1 11中的水倒入玻璃杯5 55。总共付出代价和为1 2 2 5 12251225。数据规模与约定对于40 % 40\%40%的数据满足N ≤ 10 N\le 10N≤10。对于100 % 100\%100%的数据满足1 ≤ K ≤ N ≤ 20 , C i , j ≤ 10 5 1\le K\le N\le 20,C_{i,j}\le10^51≤K≤N≤20,Ci,j​≤105说明题目译自 COCI2016-2017 CONTEST #3T3 Kroničan。C实现#includeiostream#includecstdio#includecstring#includealgorithmusingnamespacestd;constintN21;intn,m,a[N][N],dp[1N];intmain(){cinnm;for(inti1;in;i)for(intj1;jn;j)cina[i][j];memset(dp,0x3f,sizeofdp);dp[0]0;for(registerinti1;i(1n);i)for(registerintj0;jn;j)if(i(1j))//判断第j1位是不是1for(registerintk0;kn;k)if(!(i(1k)))//判断第k1位是不是0dp[i]min(dp[i],dp[i^(1j)]a[j1][k1]);intans-1u/2;//即2的31次方-1for(registerinti0;i(1n);i){intcnt0;for(registerintj0;jn;j)if(!(i(1j)))cnt;//统计有几位是0if(cntm)ansmin(ans,dp[i]);}coutansendl;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容