Poj Solution 2421

http://poj.org/problem?id=2421

//* @author: 82638882@163.com
import java.util.Scanner;
public class Main
{
 static int[] bin;
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int a=in.nextInt();
  int[][] p=new int[a][a];
  for(int i=0;i< a;i++)
   for(int j=0;j< a;j++)
    p[i][j]=in.nextInt();
  bin=new int[a];
  for(int i=0;i< a;i++)
    bin[i]=i;
  int n=in.nextInt();
  while((n--)!=0)
  {
   int w1=in.nextInt();
   int w2=in.nextInt();
   union(w1-1,w2-1);
  }
  int ans=0,min,tag,tag2;
  lv: while(true)
      {
    min=9999999;
    tag=-1;tag2=-1;
    boolean bb=false;
    for(int i=0;i< a-1;i++)
    {        
      for(int j=i+1;j< a;j++)
      {
       if(root(j)!=root(i))
       {
        if(p[i][j]< min)
         {
        min=p[i][j];
        tag=j;tag2=i;
          }
        bb=true;
       }    
      }
    if(!bb) break lv;    
    }
    union(tag2,tag);
    ans+=min;
      }
      System.out.println(ans);
    }
    
  static int  root(int b)
  {
   int a=b;
   while(bin[a]!=a)
    a=bin[a];
   bin[b]=a;
   return a;
  }

 static void union(int a,int b)
 {
    int a1=root(a);
    int b1=root(b);
    if(a1==b1) return;
    if(a1>b1) bin[a1]=b1;
    else bin[b1]=a1;
  }
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *