老人家的舊書房

這是我聽完這部分後的唯一感想

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

import java.io.*;

class edge{
 private int tp[] = new int[2];
 private int cost;
 edge(int tp0,int tp1,int cost){
  tp[0] = tp0;
  tp[1] = tp1;
  this.cost = cost;
 }
 int getCost(){
  return cost;
 }
 int getTP(int which){
  return tp[which];
 }
 public String toString(){
  char tp0 = (char)('A'+tp[0]);
  char tp1 = (char)('A'+tp[1]);
  return "("+tp0+","+tp1+")"+cost;
 }
}

class graph{
 private int[] vertexs;
 private edge[] edges = new edge[200];
 private int numberofedges = 0;
 private int edgeIndex = 0;
 private int groupIndex = 1;
 graph(int n)throws IOException{
  vertexs = new int[n];
  inputGraph(n);
  sortEdges();
 }
 void inputGraph(int n)throws IOException{
  BufferedReader br = new BufferedReader(new FileReader("graph.txt"));
  String s;
  while((s=br.readLine())!=null){
   int c1 = s.charAt(0)-'A';
   int c2 = s.charAt(1)-'A';
   int ct = Integer.parseInt(s.substring(2,s.length()));
   edges[numberofedges++] = new edge(c1,c2,ct);
  }
  br.close();
 }
 void sortEdges(){
  for(int i=numberofedges-1;i>0;i--){
   for(int j=0;j<i;j++){
    if(edges[j].getCost() > edges[j+1].getCost()){
     edge e = edges[j];
     edges[j] = edges[j+1];
     edges[j+1] = e;
    }
   }
  }
 }
 edge getMinEdge(){
  for(;!(vertexs[edges[edgeIndex].getTP(0)]==0                                          //喵的，這串for迴圈是怎樣！長到靠....北邊走
   && vertexs[edges[edgeIndex].getTP(1)]==0
   ||(vertexs[edges[edgeIndex].getTP(0)]!=vertexs[edges[edgeIndex].getTP(1)]));edgeIndex++);
  if(vertexs[edges[edgeIndex].getTP(0)]==0 && vertexs[edges[edgeIndex].getTP(1)]==0){
   vertexs[edges[edgeIndex].getTP(0)] = vertexs[edges[edgeIndex].getTP(1)] = groupIndex;
   groupIndex++;
  }else{
   int l,g; //l = smaller , g = larger group ID
   if(vertexs[edges[edgeIndex].getTP(0)] > vertexs[edges[edgeIndex].getTP(1)]){
    l = vertexs[edges[edgeIndex].getTP(1)];
    g = vertexs[edges[edgeIndex].getTP(0)];
   }else{
    l = vertexs[edges[edgeIndex].getTP(0)];
    g = vertexs[edges[edgeIndex].getTP(1)];
   }
   for(int k=0;k<vertexs.length;k++)
    if(vertexs[k]==1)
     vertexs[k] = g;
  }
  return edges[edgeIndex++];
 }
}

public class KruskalMst{
 public static void main(String[] alio)
  throws IOException{
   int totalCost = 0;
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.println("有幾個頂點？");
   int vv = Integer.parseInt(br.readLine());
   graph g = new graph(vv);
   for(int i=1;i<vv;i++){
    edge e = g.getMinEdge();
    totalCost += e.getCost();
    System.out.println(e);
   }
   System.out.println("total cost = "+totalCost);
  }
}
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝