P1669 Bad Cowtractors S网页链接P1669 Bad Cowtractors S题目描述奶牛贝茜被雇去建设N ( 2 ≤ N ≤ 10 3 ) N(2\le N\le 10^3)N(2≤N≤103)个牛棚间的互联网。她已经勘探出M ( 1 ≤ M ≤ 2 × 10 4 ) M(1\le M\le 2\times 10^4)M(1≤M≤2×104)条可建的线路每条线路连接两个牛棚而且会花费C ( 1 ≤ C ≤ 10 5 ) C(1\le C\le 10^5)C(1≤C≤105)。农夫约翰吝啬得很他希望建设费用最少甚至他都不想给贝茜工钱。贝茜得知工钱要告吹决定报复。她打算选择建一些线路把所有牛棚连接在一起让约翰花费最大。但是她不能造出环来这样约翰就会发现。输入格式第1 11行N NNM MM。第2 22到M 1 M1M1行三个整数表示一条可能线路的两个端点和费用。输出格式一行表示最大的花费。如果不能建成合理的线路就输出− 1 -1−1。输入输出样例 #1输入 #15 8 1 2 3 1 3 7 2 3 10 2 4 4 2 5 8 3 4 6 3 5 2 4 5 17输出 #142说明/提示2 ≤ N ≤ 10 3 2\le N\le 10^32≤N≤1031 ≤ M ≤ 2 × 10 4 1\le M\le 2\times 10^41≤M≤2×1041 ≤ C ≤ 10 5 1\le C\le 10^51≤C≤105。解题思路本题是最大生成树问题。农夫约翰想最小化成本而贝茜要报复选择一些边将所有牛棚连接成树且总费用最大。需要注意不能形成环因此最终选出的边必须构成一棵生成树。若图不连通输出-1。1. 问题等价转化给定一个无向带权图要求选择若干条边使得所有节点连通且无环即形成生成树并且边的总权值最大。这与最小生成树问题相反只需将 Prim 或 Kruskal 算法中的“取最小”改为“取最大”即可。若图本身不连通则不存在生成树输出-1。2. 算法实现Prim 算法求最大生成树采用类似 Prim 的贪心策略从节点1 11开始逐步扩展最大生成树。初始化邻接矩阵mp[i][j]存储两点间的最大边权可能有重边取最大值不存在的边权设为极小值-114。距离数组d[i]表示节点i ii到当前已选生成树集合的最大边权。初始时将1 11号节点视为已选d[i] mp[i][1]。循环n − 1 n-1n−1次每次选择一个新的节点加入生成树在所有未选节点used[j]false中找出d[j]最大的节点id。若找不到id -1说明图不连通返回false。将id标记为已选累加边权res d[id]。用节点id到其他未选节点的边权更新d[j]d[j] max(d[j], mp[id][j])。结果输出若 Prim 过程成功完成输出总权值res否则输出-1。3. 复杂度分析时间复杂度Prim 算法使用邻接矩阵外层循环n − 1 n-1n−1次每次找最大d和更新均需O ( n ) O(n)O(n)总复杂度O ( n 2 ) O(n^2)O(n2)。本题n ≤ 1000 n \le 1000n≤1000完全可行。空间复杂度邻接矩阵O ( n 2 ) O(n^2)O(n2)距离与标记数组O ( n ) O(n)O(n)。总结将最小生成树 Prim 算法中的“最小值”改为“最大值”即可求解最大生成树。注意处理不连通的情况以及重边时保留最大边权。算法简单高效适合本题数据范围。代码简要说明mp为邻接矩阵初始化为极小值-114读入边时取max保留最大权值。prim()函数执行最大生成树构建若不连通返回false。主函数根据prim()的结果输出最大花费或-1。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll mp[2005][2005],n,m,d[2005],res,used[2005];boolprim(){for(ll i2;in;i)d[i]mp[i][1];for(ll i1;in;i){ll id-1,mx-114;for(ll j2;jn;j){if(!used[j]d[j]mx){idj;mxd[j];}}if(id-1)returnfalse;used[id]1;resd[id];for(ll j1;jn;j){d[j]max(mp[id][j],d[j]);}}returntrue;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnm;ll u,v,w;for(ll i1;in;i)for(ll j1;jn;j)mp[i][j]mp[j][i]-114;for(ll i1;im;i){cinuvw;mp[u][v]mp[v][u]max(w,mp[u][v]);}if(!prim())cout-1;elsecoutres;return0;}