UVA 10600 ACM Contest and Blackout(次小生成树)

题意：
　　给你点和边，求出最小生成树和次小生成树。
思路：
　　先求一次最小生成树，然后标记每一条边，依次删除，再求最小生成树，从中找到最小的就是次小生成树了。
代码：
  1 import java.util.Scanner;
  2 import java.util.Comparator;
  3 import java.util.Arrays;
  4 
  5 class Node{
  6     public int u, v, w, mark;
  7 }
  8 //结构排序
  9 class mycmp implements  Comparator<Node>{
 10     public int compare(Node A, Node B){ 
 11                 return A.w - B.w;  
 12       }  
 13 }
 14 public class Main {
 15     final static int MAXN = 10000 + 13;
 16     final static int INF = 0x3f3f3f3f;
 17     static int[] pre = new int[MAXN];
 18     static Node[] map = new Node[MAXN];
 19     public static void main(String[] args){
 20         Scanner sc = new Scanner(System.in);
 21         int T = sc.nextInt();
 22         while(T != 0){
 23             int N,M;
 24             N = sc.nextInt();
 25             M = sc.nextInt();
 26             for(int i = 1; i <= M; i++){
 27                 map[i]=new Node();  
 28                 map[i].u = sc.nextInt();
 29                 map[i].v = sc.nextInt();
 30                 map[i].w = sc.nextInt();
 31                 map[i].mark = 0;
 32             }
 33             mst(N);
 34             Arrays.sort(map, 1, M + 1, new mycmp());
 35             int mst = ksu(N, M);   // MST
 36             int sst = INF + 1;    //SST 初始化
 37             for(int i = 1; i <= M; i++){ //求SST
 38                 if(map[i].mark == 1){  //这条边属于MST
 39                     mst(N);
 40                     int temp = ksu(N, M, i);       //删除一条边后得到的结果、如果大于 0 说明构造成功，否则构造失败
 41                     if(temp < sst && temp != -1){ 
 42                         sst = temp;
 43                     }
 44                 }
 45             }
 46             System.out.println(mst + " " + sst);
 47             T--;
 48         }
 49         sc.close();
 50     }
 51     public static int ksu(int N, int M){ //求MST
 52         int cnt = 0;
 53         int ans= 0;
 54         for(int i = 1; i <= M; i++){
 55             int fu = Find(map[i].u);
 56             int fv = Find(map[i].v);
 57             if(fu != fv){
 58                 ans += map[i].w;
 59                 cnt++;
 60                 pre[fv] = fu;
 61                 map[i].mark = 1;   //标记
 62             }
 63             if(cnt == N - 1){
 64                 return ans;
 65             }
 66         }
 67         return ans;
 68     }
 69     public static int ksu(int N, int M,int mark){  //删除 mark 这条边 求 MST
 70         int ans= 0;
 71         int cnt = 0;
 72         for(int i = 1; i <= M; i++){
 73             if(i == mark) continue;    //删除
 74             int fu = Find(map[i].u);
 75             int fv = Find(map[i].v);
 76             if(fu != fv){
 77                 ans += map[i].w;
 78                 cnt++;
 79                 pre[fv] = fu;
 80             }
 81             if(cnt == N - 1){
 82                 return ans;
 83             }
 84         }
 85         return -1;
 86     }
 87     public static int Find(int x){
 88         return x == pre[x] ? x : (pre[x] = Find(pre[x]));
 89     }
 90     public static void debug(int M){
 91         for(int i = 1; i <= M; i++){
 92             System.out.println(i + " " + map[i].u + " " + map[i].v + " " + map [i].w + " "+ map[i].mark);
 93         }
 94     }
 95     public static void mst(int N){
 96         for(int i = 1; i <= N; i++){
 97             pre[i] = i;
 98         }
 99     }
100 }