POJ 3723

最大生成树

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
#include<stack>
#include<map>
#include<queue>
#include<list>
#include<vector>
using namespace std;
const int maxn = 50000 + 131;
const int maxm = 10000 + 131;
struct Edge {int u, v, cost;Edge(int u_, int v_, int c_): u(u_), v(v_), cost(c_) {}bool operator < (const Edge a) const {return cost > a.cost;}
};
vector<Edge> G;/// Uinon-Set
int Pre[maxm * 2], Num[maxm * 2];
void Init(int N) {for(int i = 0; i <= N; ++i)Pre[i] = i;
}int Find(int x) {/*int r = x;while(r != Pre[r]) r = Pre[r];return Pre[x] = r;*/if(x == Pre[x]) return x;else return Pre[x] = Find(Pre[x]);
}bool Union(int x, int y) {int ax = Find(x), ay = Find(y);if(ax == ay) return false;Pre[ax] = ay;return true;
}/// MST;
typedef long long LL;
LL Sum = 0;
LL Kusual(int N,int R)
{Sum = 0;sort(G.begin(),G.end());Init(N);for(int i = 0; i < G.size(); ++i){int u = G[i].u, v = G[i].v;if(Union(u, v)){Sum +=(LL) (G[i].cost);}}return Sum;
}int main()
{int N, M, R;int x, y, d;int T;scanf("%d",&T);while(T--){scanf("%d%d%d", &N, &M, &R);G.clear();for(int i = 0; i < R; ++i){scanf("%d%d%d", &x, &y, &d);G.push_back(Edge(x,y+N,d));G.push_back(Edge(y+N,x,d));}//cout << Sum << endl;//Sum = 0;printf("%lld\n",(LL)(10000 * (N+M)) - Kusual(N+M,R));}
}