Kruskal（）生成树模板+并查集算法：
//改进一下，适合一最小最大生成树
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_E=20100;//注意范围一定要开大
struct edge{int u,v;long long cost;
}es[MAX_E];
int n,m;//int V,E;//对应顶点数目和边数目
int tree;
int par[MAX_E],rank[MAX_E];
bool cmp(const edge& e1,const edge& e2){return e1.cost<e2.cost;
}
void init(int n){for(int i=0;i<n;i++){par[i]=i;rank[i]=0;}
}
int find(int x){if(par[x]==x)return x;else return par[x]=find(par[x]);
}
void unite(int x,int y){x=find(x);y=find(y);if(x==y)return ;if(rank[x]<rank[y]){par[x]=y;}else{par[y]=x;if(rank[x]==rank[y])rank[x]++;}
}
bool same(int x,int y){return find(x)==find(y);
}
long long Kruskal(){sort(es,es+m,cmp);init(n);tree=n;long long res=0;for(int i=0;i<m;i++){edge e=es[i];if(!same(e.u,e.v)){unite(e.u,e.v);res+=e.cost;tree--;//tree用于判断森林是否可以构成树
//if(tree>=2)//cout<<"can not "<<endl;
//else cout<<ans<<endl;}}return res;
}对应题目：POJ2377；
思路：取反，es[i].cost=-es[i].cost;//同样适合于最大生成树的算法，最后对结果取符号即可.
注意：不要runtime error，内存空间结合题目开辟，Kruskal()返回类型用long long.
主方法如下以及将主方法与上面的代码结合即可满足要求：
int main(){cin>>n>>m;//顶点数目和边数目 for(int i=0;i<m;i++){cin>>es[i].u>>es[i].v>>es[i].cost;es[i].cost=-es[i].cost;}long long ans=-Kruskal();if(tree>1)cout<<"-1"<<endl;elsecout<<ans<<endl;}
/*Sample Input//求最大路径长度之和，可以考虑转化
5 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
Sample Output
42
Hint
OUTPUT DETAILS:The most expensive tree has cost 17 + 8 + 10 + 7 = 42. It uses the following connections: 4 to 5, 2 to 5, 2 to 3, and 1 to 3.*/