次小生成树问题探讨
??????? 只要最小生成树和次小生成树权值和一样就唯一。因此得出如下算法，首先计算出最小生成树T，然后对最小生成树上任意不相邻的两个点 uv添加最小生成树以外的存在的边形成环，然后寻找u与v之间最小生成树上最长的边删去，计算map[i][j]与 maxd[i][j差值，求出最小的来，如果是0，就说明MST和次小生成树一样。
//顶点数100，看成了1000，一个MLE，改了立马AC，嘿嘿
//这道题目，AC率很低
import java.util.Scanner;
public class POJ1679 {static int maxn = 105;
static int[][] map = new int[maxn][maxn];
static int[][] maxd = new int[maxn][maxn];
static int[] father = new int[maxn];
static int[] dist = new int[maxn];
static boolean[] vis = new boolean[maxn];
static int n,m;
public static void main(String[] args) {Scanner sc= new Scanner(System.in);
int num = sc.nextInt();
int u,v,w;
while(num-->0) {n = sc.nextInt();
m = sc.nextInt();
for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(i==j) {map[i][j] = 0;
}else {map[i][j] = 0x3f3f3f3f;
}
maxd[i][j] = -1;
}
}
for(int i=0; i<m; i++) {u = sc.nextInt();
v = sc.nextInt();
w = sc.nextInt();
map[u][v] = w;
map[v][u] = w;
}
int ans = prime();
int min = 0x3f3f3f3f;
for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) {boolean tag = i!=j&&map[i][j]!=0x3f3f3f3f
&&father[i]!=j&&father[j]!=i;
if(tag) { if(min>map[i][j]-maxd[i][j]) {min = map[i][j]-maxd[i][j];
}
}
}
}
if(0==min) { System.out.println("Not Unique!"); }else {System.out.println(ans);
}
}
}
private static int prime() {int ans = 0;
for(int i=1; i<=n; i++) {dist[i] = map[1][i];
father[i] = 1;
vis[i] = false;
}
vis[1] = true;
//存放MST节点
int stack[] = new int[n+1];
int top = 0;
stack[top++] = 1;
for(int i=1; i<n; i++) {int next = 1;
int min = 0x3f3f3f3f;
for(int j=1; j<=n; j++) { if(!vis[j]&&min>dist[j]) {next = j;
min = dist[j];
}
}
vis[next] = true;
ans += min;
//dp
for(int k=0; k<top; k++) {maxd[next][stack[k]] = maxd[stack[k]][next]
= Math.max(min,maxd[father[next]][stack[k]]);
}
stack[top++] = next;
for(int t=1; t<=n; t++) { if(!vis[t]&&dist[t]>map[next][t]) {dist[t] = map[next][t];
father[t] = next;
}
}
}
return ans;
}
}
??????? 接下来该看数据挖掘十大算法了。