极简网站设计,电脑上制作网页的软件,做淘宝联盟网站要多少钱?,网线制作的标准及方法局域网
题目
就是一个图#xff0c;求最小生成树#xff0c;然后求被去除的边的价值。
输入
用线来表示联通 5 5 1 2 8 1 3 1 1 5 3 2 4 5 3 4 2
输出
去除的边的总价值 8 解题思路
求出最小生成树的价值然后线的总值减去最小生成树的价值 代码
#include求最小生成树然后求被去除的边的价值。
输入
用线来表示联通 5 5 1 2 8 1 3 1 1 5 3 2 4 5 3 4 2
输出
去除的边的总价值 8 解题思路
求出最小生成树的价值然后线的总值减去最小生成树的价值 代码
#includecstdio
using namespace std;
int n,k,cost[101][101],lowcost[101],x,y,w,s,last,maxs;
bool ok[101];
int main()
{scanf(%d%d,n,k);for (int i1;in;i)for (int j1;jn;j) cost[i][j]23333333;//初始化for (int i1;ik;i){scanf(%d%d%d,x,y,w);cost[x][y]w;cost[y][x]w;//联通maxsw;//求总值}for (int i1;in;i) lowcost[i]cost[1][i];//每个点到集合的最小值ok[1]true;//封路for (int i2;in;i){int k0,mins23333333;for (int j1;jn;j)if (!ok[j] lowcost[j]mins){minslowcost[j];kj;}//找最近的店ok[k]true;//标记slowcost[k];//求和for (int j1;jn;j)if (lowcost[j]cost[k][j]) lowcost[j]cost[k][j]; //修正每个点到集合的最小值}printf(%d,maxs-s);//输出
}
