P1550 [USACO08OCT] Watering Hole G 小结

题目概述Farmer John 的农场缺水了。他决定将水引入到他的 n 个田地。他准备通过挖若干井并在各块田中修筑水道来连通各块田地以供水。在第 i 号田中挖一口井需要花费 Wi​ 元。连接 i 号田与 j 号田需要 Pi,j​Pj,i​Pi,j​元。请求出 FJ 需要为使所有田地都与有水的田地相连或拥有水井所需要的最少钱数。输入格式第一行为一个整数 n。接下来 n 行每行一个整数 Wi​。接下来 n 行每行 n 个整数第 i 行的第 j 个数表示连接 i 号田和 j 号田需要的费用 Pi,j​。输出格式输出最小开销。思路本题不能简单只修水渠或只挖井部分田地挖井、其余靠水渠连通整体最优因此采用超级源点 最小生成树 Kruskal新增超级源点 0 代表水源在第i块田地单独挖井等价于虚拟点0和点i之间连一条边边权等于该地挖井花费Wi​用这条边代表就地取水田地之间建边i、j两块田地修水渠连通在两点间连边边权是修路费用Pi,j​为避免重复存无向边只枚举ij问题转化总共有n1个点0∼n全连通的最小开销等价于整张图的最小生成树总权n1个点需要选出n条边算法流程全部边按权从小到大排序用并查集依次选边两点不在同一集合就合并并累加边权凑齐n条边后累加和就是答案。代码:#includebits/stdc.h using namespace std; int ans 0 , cnt 0 , t 0 , fa[10005] , p , w; struct edge{ int x, y, z; }e[1000005]; int find(int x){ if (fa[x] x){ return x; } else { return fa[x] find(fa[x]); } } bool cmp(edge a, edge b){ return a.z b.z; } int main(){ int n; cin n; for (int i 0;i n;i){ fa[i] i; } for (int i 1;i n;i){ cin w; e[t] {0 , i , w}; } for (int i 1;i n;i){ for (int j 1;j n;j){ cin p; if (i j){ e[t] {i , j , p}; } } } sort(e 1 , e t 1 , cmp); for (int i 1;i t;i){ int fx find(e[i].x); int fy find(e[i].y); if (fx ! fy){ fa[fy] fx; ans e[i].z; cnt; if (cnt n){ break; } } } cout ans; return 0; }