# Poj Solution 3723

```http://poj.org/problem?id=3723

//* @author:
//Kruskal �㷨:
import java.io.*;
import java.util.*;

class cin
{
static int leave=0;
static StringTokenizer st;
static int nextInt() throws Exception
{
while (leave==0)
{
leave=st.countTokens();
}
leave--;
return Integer.parseInt(st.nextToken());
}
}

class E
{
int weight,from,to;
void init(int x,int y,int z)
{
weight=z;
from=x;
to=y;
}
}

class Cmp implements Comparator
{
public int compare(Object a,Object b)
{
int c=((E)a).weight-((E)b).weight;
if(c< 0)return -1;
return 1;
}
}

class Set
{
int father[];
int num;
Set(int n)
{
num=n;
father=new int[n];
this.clear();
}

void clear()
{
int i;
for(i=0;i< num;i++)father[i]=i;
}

int findF(int x)
{
int t=x;
while(t!=father[t])
{
t=father[t];
}
while(x!=father[x])
{
father[x]=t;
x=father[x];
}
return t;
}

boolean union(int x,int y)
{
int fx=findF(x),fy=findF(y);
if(fx==fy)return false;
father[fy]=fx;
num--;
return true;
}
}

class Kruskal
{
E e[];
int numOfE,numOfTree,i,j,numOfD;
Set points;

Kruskal(E a[],int m,int n)
{
e=a;
numOfE=m;
numOfD=n;
points=new Set(numOfD);
}

int cost()
{
int sum=0,f1,f2;
Arrays.sort(e,new Cmp());
for(i=0;i< numOfE;i++)
{
if(points.num==1)break;
if(points.union(e[i].from,e[i].to))
{
sum+=e[i].weight;
}
}
return sum+10000*points.num;
}

}
public class Main {
public static void main(String args[]) throws Exception
{
int g,b,r,t,i;
E e[];
t=cin.nextInt();
Kruskal data;
while((t--)>0)
{
g=cin.nextInt();
b=cin.nextInt();
r=cin.nextInt();
e=new E[r];
for(i=0;i< r;i++)
{
e[i]=new E();
e[i].init(cin.nextInt(),cin.nextInt()+g,10000-cin.nextInt());
}
data=new Kruskal(e,r,g+b);
System.out.println(data.cost());
}
}
}
```
This entry was posted in poj. Bookmark the permalink.