有人做网站推广吗,HTML转换WordPress文件,北京网站建设公司拟,客厅装修效果图片大全城市中有 n n n个路口#xff0c;交叉路口之间有道路相连#xff0c;两个交叉路口之间最多有一条道路相连接。这些道路是双向的#xff0c;且有一个分值。现在要求对道路进行构造#xff0c;提出下面的要求#xff1a;
改造的那些道路能够把所有的交叉路口直接或间接的连…城市中有 n n n个路口交叉路口之间有道路相连两个交叉路口之间最多有一条道路相连接。这些道路是双向的且有一个分值。现在要求对道路进行构造提出下面的要求
改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
在满足要求 1 的情况下改造的道路尽量少。
在满足要求 1、2 的情况下改造的那些道路中分值最大的道路分值尽量小。求选出了几条道路分值最大的那条道路的分值是多少。 本题主要是最小生成树的运用第一问求道路数每个点都能直接或间接连接最少情况就是一棵树所以直接输出 n − 1 n-1 n−1就好了。对于分值最大的道路分值尽量小可能想到二分法来求但其实不需要我们只需要按照最小生成树的思路来构造一棵树整棵树都是最小的那么最大值一定小了。
#includebits/stdc.h
using namespace std;
struct node
{int u,v,w;
}a[50010];
int f[50010];
int n,m,maxx-99999,ans0;
bool cmp(node x,node y)
{return x.wy.w;
}
int find(int k)
{if(kf[k])return k;else return f[k]find(f[k]);
}
void kus()
{for(int i1;im;i){int Ufind(a[i].u);int Vfind(a[i].v);if(UV)continue;maxxmax(maxx,a[i].w);ans;if(U!V)f[U]V; if(ansn-1)break;}
}
int main()
{cinnm;for(int i1;in;i)f[i]i;for(int i1;im;i)cina[i].ua[i].va[i].w;sort(a1,am1,cmp);kus();coutn-1 maxxendl;return 0;
}
