本文共 1415 字，大约阅读时间需要 4 分钟。
最大生成树
#include #include #include #include #include #include #include #include #include #include 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 G;/// Uinon-Setint 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)); }}
转载于:https://www.cnblogs.com/aoxuets/p/4944748.html