(UVA) 11631 - Dark roads [MST Kruskal]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=2678

MST 最小生成樹

這個一定要用Kruskal 才行

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

const int MAX_N = 2e5+6;
const int MAX_M = 2e5+6;

struct Edge {
 int a,b,c;
} edg[MAX_M];

Edge MP(int _a,int _b,int _c) {
 Edge ret;
 ret.a=_a;
 ret.b=_b;
 ret.c=_c;
 return ret;
}

bool operator<(const Edge &e1,const Edge &e2) {
 return e1.c<e2.c;
}

struct Disjointset {
 int p[MAX_N];
 void init(int n) {
  for (int x=0;n>=x;x++) p[x]=x;
 }
 int Find(int x) {
  return p[x]==x?x:p[x]=Find(p[x]);
 }
 void Union(int x,int y) {
  p[Find(x)]=Find(y);
 }
} djs;

int Kruskal(int n,int m) {
 int ret=0;
 sort(edg,edg+m);
 djs.init(n);
 for (int i=0;;i++) {
  while (i<m && djs.Find(edg[i].a) == djs.Find(edg[i].b)) i++;
  if (i==m) break;
  ret+=edg[i].c;
  djs.Union(edg[i].a,edg[i].b);
 }
 return ret;
}

int main () {
 int m,n;
 while (scanf("%d %d",&n,&m) != EOF) {
  if (n==0&&m==0) break;
  int sum=0;
  for (int x=0;m>x;x++) {
   int i,j,k;
   scanf("%d %d %d",&i,&j,&k);
   edg[x]=MP(i,j,k);
   sum+=k;
  }
  printf("%d\n",sum-Kruskal(n,m));
 }
}
/*
7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
0 0

*/