ajax网站,温州制作网站公司,免费新闻源发布平台,wordpress 连接丢失.保存已被禁用_直到您重新连接.题目
一个无向图#xff0c;求最小生成树里权值最大的那条边
输入
第一行有两个整数n,m表示有n个店#xff0c;m条边。接下来m行是对每条边的描述#xff0c;u, v, c表示点u和v之间有边#xff0c;权值为c。(1≤n≤300#xff0c;1≤c≤10000) 4 5 1 2 3 1 4 5 2 4…题目
一个无向图求最小生成树里权值最大的那条边
输入
第一行有两个整数n,m表示有n个店m条边。接下来m行是对每条边的描述u, v, c表示点u和v之间有边权值为c。(1≤n≤3001≤c≤10000) 4 5 1 2 3 1 4 5 2 4 7 2 3 6 3 4 8
输出
两个整数s, max表示你有几条边权值最大的那条边的权值是多少。 3 6 解题思路
我们知道最小生成树一点是n-1条边的然后求最大值很简单 代码
#includecstdio
#includeiostream
using namespace std;
int n,k,cost[301][301],lowcost[301],x,y,w,s,last,maxs;
bool ok[301];
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;//联通}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;//封路smax(s,lowcost[k]);//求最大值for (int j1;jn;j)if (lowcost[j]cost[k][j]) lowcost[j]cost[k][j]; //修正离集合最近的距离}printf(%d %d,n-1,s);//输出
}
