Out of Hay.(POJ-2395)

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<map> using namespace std; int n,m,a,b,c,par[1005],rankk[1005],max_road; struct edge { int u,v,cost; edge(int u=0,int v=0,int cost=0) : u(u),v(v),cost(cost) {} }; bool cmp(const edge& e1,const edge& e2) { return e1.cost<e2.cost; } edge es[20005]; void init(int n) { for(int i=1;i<=n;i++) { par[i] = i; rankk[i] = 0; } } int findd(int x) { return par[x] == x ? x : par[x] = findd(par[x]); } void unite(int x,int y) { x = findd(x); y = findd(y); if(x==y) return ; if(rankk[x] < rankk[y]) { par[x] = y; } else { par[y] = x; if(rankk[x] == rankk[y]) rankk[x] ++ ; } } bool same(int x,int y) { return findd(x) == findd(y); } int kruskal() { sort(es,es+m,cmp); init(n); int res = 0; for(int i=0;i<m;i++) { edge e = edge(es[i].u,es[i].v,es[i].cost); if(!same(e.u,e.v)) { unite(e.u,e.v); res += e.cost; max_road = max(max_road,e.cost); } } return res; } int main() { scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); es[i] = edge(a,c); } max_road = ⑴; int sum = kruskal(); printf("%d ",max_road); return 0; }