东东在老家农村无聊，想种田。农田有 n 块，编号从 1~n。种田要灌氵
众所周知东东是一个魔法师，他可以消耗一定的 MP 在一块田上施展魔法，使得黄河之水天上来。他也可以消耗一定的 MP 在两块田的渠上建立传送门，使得这块田引用那块有水的田的水。 (1<=n<=3e2)
黄河之水天上来的消耗是 Wi，i 是农田编号 (1<=Wi<=1e5)
建立传送门的消耗是 Pij，i、j 是农田编号 (1<= Pij <=1e5, Pij = Pji, Pii =0)
东东为所有的田灌氵的最小消耗
输入
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0输出
9
kruskal算法和并查集，关于Kruskal算法可以看我的另一篇博客：Kruskal最小生成树算法
（写得不好，望指摘(#^.^#)
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
int host[310];//农田编号
int n,mass,lop=0,sum=0;//农田数量,天外加水重量，lop，结果
int px,py;
struct edge{
int u,v,w;//起点，到达点，权重
bool operator<(const edge &eg){
return w<eg.w;//按照权重升序排序
}
};
edge e[maxn];
void add_edge(int start,int to,int wei){
e[lop].u=start;
e[lop].v=to;
e[lop].w=wei;
lop++;
}
int unionsearch(int root){
int son,temp;
son=root;
while(root != host[root])
root=host[root];
while(son != root){
temp=host[son];
host[son]=root;
son=temp;
}
return root;
}
void kruskal(){//克鲁斯卡算法
sort(e,e+lop);//排序找到最小的权重
int tag=0;
for(int i=0;i<lop;i++){
if(tag==n) break;//没有农田
px=unionsearch(e[i].u);py=unionsearch(e[i].v);
if(px != py){//如果两个点不在一棵树
host[py]=px;
tag++;
sum+=e[i].w;
}
}
cout<<sum<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=0;i<=n;i++)
host[i]=i;
for(int i=1;i<=n;i++){
cin>>mass;
add_edge(0,i,mass);
add_edge(i,0,mass);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mass;
add_edge(i,j,mass);
}
}
kruskal();
return 0;
}在一个集中式网络中，存在一个根节点，需要长时间接收其余所有节点传输给它的反馈数据。
[题目描述]
存在一个n节点的网络图，编号从1到n。该网络的传输是全双工的，所以是无向图。
如果两节点Vi , Ui 相连，表明Vi , Ui 之间可以互相收发数据，边权是传输数据所需时间 ti 。现在每个节点需要选择-条路径将数据发送到root 号节点。希望求出一个最优的树结构传输图，使得完成这个任务所需要的时间最少。root 节点只能接收数据，其余任何一个节点可以将数据传输给另外的一一个节 点，但是不能将数据传输给多个节点。
所有节点可以接收多个不同节点的数据。
一个树结构传输图的传输时间为Tmax，其中Tmax = max(Th), h为接收点在树中的深度，Th= max(th,j), th,j 表示 j 条不同的边，这 j 条边接收点的深度都为h。
[输入格式]
从标准输入读入数据。
输入的第1行包含一个正整数n,保证n≤5x 10^4。
输入的第2行包含一个正整数m,保证m≤10^5.
输入的第3行包含一个正整数root,保证roo≤5x 10^4。
[输出格式]
输出到标准输出。
输出仅有一行， 包含一个 正整数ans,表示最优的树结构流水线所耗时Tmax。
图片
Example
Input
4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2
Output
4
解：首先明确了题意就简单了，这道题运用并查集和Kruskal算法，利用贪心
把最大的边去掉，保留最小边，那么再求出最小中的最大
然后这道题太模糊了，自己画了一张图，2333代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=5e4+10;
int pre[maxn];
int n,m,root;//n个节点，m 条边，根节点
int px,py,ans=0;
struct edge{
int u,v,w;//起点，到达点，权重
bool operator<(const edge &eg){
return w<eg.w;//按照权重升序排序
}
};
edge e[maxn*2];
int unionsearch(int rot){
int son,temp;
son=rot;
while(rot != pre[rot])
rot=pre[rot];
while(son != rot){
temp=pre[son];
pre[son]=rot;
son=temp;
}
return rot;
}
void kruskal(){//克鲁斯卡算法
sort(e+1,e+m+1);//排序找到最小的权重
int tag=0;
for(int i=1;i<=m;i++){
px=unionsearch(e[i].u);py=unionsearch(e[i].v);
if(px != py){ //木有成环，可以构成树
pre[py]=px;
ans=max(ans,e[i].w);
tag++;
}
if(tag==n-1) break;
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>root;
for(int i=1;i<=n;i++)
pre[i]=i;//每个节点都是祖宗
for(int i=1;i<=m;i++)//输入起点，到达点，边权，即构造图过程
cin>>e[i].u>>e[i].v>>e[i].w;
kruskal();
return 0;
}