給出一個帶邊權(quán)的無向圖G，設(shè)其最小生成樹為T，求出圖G的與T
不完全相同的邊權(quán)和最小的生成樹（即G的次小生成樹）。一個無向圖的兩棵生成樹不完全相同，當且僅當這兩棵樹中至少有一條邊不同。注意，圖G可能不連通，可能有平行邊，但一定沒有自環(huán)（其實對于自環(huán)也很好處理：直接舍棄。因為生成樹中不可能出現(xiàn)自環(huán)）。
【具體題目】
URAL1416（注意，這一題的邊數(shù)M的范圍沒有給出，視為124750）
【分析】
定義生成樹T的一個可行變換(-E1, +E2)：將T中的邊E1刪除后，再加入邊E2（滿足邊E2原來不在T中但在G中），若得到的仍然是圖G的一棵生成樹，則該變換為可行變換，該可行變換的
代價為(E2權(quán)值 - E1權(quán)值)。這樣，很容易證明，G的次小生成樹就是由G的最小生成樹經(jīng)過一個代價最小的可行變換得到。進一步可以發(fā)現(xiàn)，
這個代價最小的可行變換中加入的邊E2的兩端點如果為V1和V2，那么E1一定是原來最小生成樹中從V1到V2的路徑上的權(quán)值最大的邊。
這樣，對于本題就有兩種算法了：（以下的T全部指G的最小生成樹）
（1）Prim：
設(shè)立數(shù)組F，F(xiàn)[x][y]表示T中從x到y(tǒng)路徑上的最大邊的權(quán)值。F數(shù)組可以在用Prim算法求最小生成樹的過程中得出。每次將邊(i, j)加入后（j是新加入樹的邊，i=c[j]），枚舉樹中原有的每個點k（包括i，但不包括j），則F[k][j]=max{F[k][i], (i, j)邊權(quán)值}，又由于F數(shù)組是對稱的，可以得到F[j][k]=F[k][j]。然后千萬記住將圖G中的邊(i, j)刪除（就是將鄰接矩陣中(i, j)邊權(quán)值改為∞）！因為T中的邊是不能被加入的。等T被求出后，所有的F值也求出了，然后，枚舉點i、j，若鄰接矩陣中邊(i, j)權(quán)值不是無窮大（這說明i、j間存在不在T中的邊），則求出{(i, j)邊權(quán)值 - F[i][j]}的值，即為加入邊(i, j)的代價，求最小的總代價即可。
另外注意三種特殊情況：【1】圖G不連通，此時最小生成樹和次小生成樹均不存在。判定方法：在擴展T的過程中找不到新的可以加入的邊；【2】圖G本身就是一棵樹，此時最小生成樹存在（就是G本身）但次小生成樹不存在。判定方法：在成功求出T后，發(fā)現(xiàn)鄰接矩陣中的值全部是無窮大；【3】圖G存在平行邊。這種情況最麻煩，因為這時代價最小的可行變換(-E1, +E2)中，E1和E2可能是平行邊！因此，只有建立兩個鄰接矩陣，分別存儲每兩點間權(quán)值最小的邊和權(quán)值次小的邊的權(quán)值，然后，每當一條新邊(i, j)加入時，不是將鄰接矩陣中邊(i, j)權(quán)值改為無窮大，而是改為連接點i、j的權(quán)值次小的邊的權(quán)值。
代碼：
#include <iostream>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
const int MAXN = 7000, INF = ~0U >> 2;
int n, s[MAXN][MAXN], s2[MAXN][MAXN], f[MAXN][MAXN], c[MAXN], v[MAXN], res1 = 0, res2 = 0;
bool vst[MAXN];
void init()
{
freopen("mst.in", "r", stdin);
scanf("%d", &n);
re(i, n) re(j, n) s[i][j] = s2[i][j] = INF;
int m, a, b, len;
scanf("%d", &m);
if (!m) {
if (n > 1) res1 = -INF; res2 = -INF;
return;
}
re(i, m) {
scanf("%d%d%d", &a, &b, &len); a--; b--;
if (len < s[a][b]) {s2[a][b] = s2[b][a] = s[a][b]; s[a][b] = s[b][a] = len;} else if (len < s2[a][b]) s2[a][b] = s2[b][a] = len;
}
fclose(stdin);
}
void solve()
{
re(i, n) {f[i][i] = c[i] = vst[i] = 0; v[i] = s[0][i];} vst[0] = 1;
int l0, l1 = INF, x, y, z;
re2(i, 1, n) {
l0 = INF; re(j, n) if (!vst[j] && v[j] < l0) {l0 = v[j]; x = j; y = c[j];}
if (l0 == INF) {res1 = res2 = -INF; return;}
vst[x] = 1; res1 += l0; s[x][y] = s[y][x] = INF; if (s2[x][y] < INF && s2[x][y] - l0 < l1) l1 = s2[x][y] - l0;
re(j, n) if (!vst[j] && s[x][j] < v[j]) {v[j] = s[x][j]; c[j] = x;}
re(j, n) if (vst[j] && j != x) f[j][x] = f[x][j] = max(f[j][y], l0);
}
re(i, n-1) re2(j, i+1, n) if (s[i][j] < INF) {
z = s[i][j] - f[i][j];
if (z < l1) l1 = z;
}
if (l1 == INF) res2 = -INF; else res2 = res1 + l1;
}
void pri()
{
freopen("mst.out", "w", stdout);
printf("Cost: %d\nCost: %d\n", res1 == -INF ? -1 : res1, res2 == -INF ? -1 : res2);
fclose(stdout);
}
int main()
{
init();
if (!res2) solve();
pri();
return 0;
}
效率分析：Prim算法求次小生成樹的時空復雜度均為O(N2)。（2）Kruskal：Kruskal算法也可以用來求次小生成樹。在準備加入一條新邊(a, b)（該邊加入后不會出現(xiàn)環(huán)）時，選擇原來a所在連通塊（設(shè)為S1）與b所在連通塊（設(shè)為S2）中，點的個數(shù)少的那個（如果隨便選一個，最壞情況下可能每次都碰到點數(shù)多的那個，時間復雜度可能增至O(NM)），找到該連通塊中的每個點i，并遍歷所有與i相關(guān)聯(lián)的邊，若發(fā)現(xiàn)某條邊的另一端點j在未選擇的那個連通塊中（也就是該邊(i, j)跨越了S1和S2）時，就說明最終在T中"刪除邊(a, b)并加入該邊"一定是一個可行變換，且由于加邊是按照權(quán)值遞增順序的，(a, b)也一定是T中從i到j(luò)路徑上權(quán)值最大的邊，故這個可行變換可能成為代價最小的可行變換，計算其代價為[(i, j)邊權(quán)值 - (a, b)邊權(quán)值]，取最小代價即可。注意，在遍歷時需要排除一條邊，就是(a, b)本身（具體實現(xiàn)時由于用DL邊表，可以將邊(a, b)的編號代入）。另外還有一個難搞的地方：如何快速找出某連通塊內(nèi)的所有點？方法：由于使用并查集，連通塊是用樹的方式存儲的，可以直接建一棵樹（準確來說是一個森林），用“最左子結(jié)點+相鄰結(jié)點”表示，則找出樹根后遍歷這棵樹就行了，另外注意在合并連通塊時也要同時合并樹。
對于三種特殊情況：【1】圖G不連通。判定方法：遍歷完所有的邊后，實際加入T的邊數(shù)小于(N-1)；【2】圖G本身就是一棵樹。判定方法：找不到這樣的邊(i, j)；【3】圖G存在平行邊。這個對于Kruskal來說完全可以無視，因為Kruskal中兩條邊只要編號不同就視為不同的邊。
其實Kruskal算法求次小生成樹還有一個優(yōu)化：每次找到邊(i, j)后，一處理完這條邊就把它從圖中刪掉，因為當S1和S2合并后，(i, j)就永遠不可能再是可行變換中的E2了。
代碼：
#include <iostream>
#include <stdlib.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
const int MAXN = 7000, MAXM = 130000, INF = ~0U >> 2;
struct edge {
int a, b, len, pre, next;
} ed[MAXM + MAXM];
struct edge2 {
int a, b, len, No;
} ed2[MAXM];
int n, m = 0, m2, u[MAXN], ch[MAXN], nx[MAXN], q[MAXN], res1 = 0, res2 = INF;
void init_d()
{
re(i, n) ed[i].a = ed[i].pre = ed[i].next = i;
if (n % 2) m = n + 1; else m = n;
}
void add_edge(int a, int b, int l)
{
ed[m].a = a; ed[m].b = b; ed[m].len = l; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
ed[m].a = b; ed[m].b = a; ed[m].len = l; ed[m].pre = ed[b].pre; ed[m].next = b; ed[b].pre = m; ed[ed[m].pre].next = m++;
}
void del_edge(int No)
{
ed[ed[No].pre].next = ed[No].next; ed[ed[No].next].pre = ed[No].pre;
ed[ed[No ^ 1].pre].next = ed[No ^ 1].next; ed[ed[No ^ 1].next].pre = ed[No ^ 1].pre;
}
void init()
{
freopen("mst.in", "r", stdin);
scanf("%d%d", &n, &m2);
if (!m2) {
if (n > 1) res1 = -INF;
res2 = -INF; return;
}
init_d();
int a, b, len;
re(i, m2) {
scanf("%d%d%d", &a, &b, &len);
ed2[i].No = m; add_edge(--a, --b, len);
ed2[i].a = a; ed2[i].b = b; ed2[i].len = len;
}
fclose(stdin);
}
int cmp(const void *s1, const void *s2)
{
return ((edge2 *)s1)->len - ((edge2 *)s2)->len;
}
void prepare()
{
re(i, n) u[i] = ch[i] = nx[i] = -1;
qsort(ed2, m2, 16, cmp);
}
int find(int x)
{
int r = x, r0 = x, tmp;
while (u[r] >= 0) r = u[r];
while (u[r0] >= 0) {tmp = u[r0]; u[r0] = r; r0 = tmp;}
return r;
}
void uni(int r1, int r2, int No, int l0)
{
q[0] = r1;
int j, k, l1, front, rear;
for (front=0, rear=0; front<=rear; front++) {
j = ch[q[front]];
while (j != -1) {
q[++rear] = j;
j = nx[j];
}
}
re3(i, 0, rear) {
j = q[i];
for (int p=ed[j].next; p != j; p=ed[p].next) {
k = ed[p].b;
if (p != No && find(k) == r2) {
l1 = ed[p].len - l0;
if (l1 < res2) res2 = l1;
del_edge(p);
}
}
}
u[r2] += u[r1]; u[r1] = r2; nx[r1] = ch[r2]; ch[r2] = r1;
}
void solve()
{
int r1, r2, l0, num = 0;
re(i, m2) {
r1 = find(ed2[i].a); r2 = find(ed2[i].b);
if (r1 != r2) {
l0 = ed2[i].len; res1 += l0; num++;
if (u[r1] >= u[r2]) uni(r1, r2, ed2[i].No, l0); else uni(r2, r1, ed2[i].No ^ 1, l0);
}
}
if (num < n - 1) {res1 = res2 = -INF; return;}
if (res2 == INF) res2 = -INF; else res2 += res1;
}
void pri()
{
freopen("mst.out", "w", stdout);
printf("Cost: %d\nCost: %d\n", res1 == -INF ? -1 : res1, res2 == -INF ? -1 : res2);
fclose(stdout);
}
int main()
{
init();
if (!res1 && res2 == INF) {
prepare();
solve();
}
pri();
return 0;
}
效率分析：可以證明，如果每次都選取點少的連通塊，Kruskal算法求次小生成樹的時間復雜度為O(M*(logN+logM))，空間復雜度為O(M)。
總結(jié)：顯然Prim適用于稠密圖，而Kruskal適用于稀疏圖。
下面是對于一些數(shù)據(jù)的測試結(jié)果（數(shù)據(jù)說明：第1~9個點和第15個點為稠密圖或一般圖，第10~14個點為稀疏圖）
Prim：
果/次小生成樹_Prim.jpg)
Kruskal（加入刪邊優(yōu)化）：
果/次小生成樹_Kruskal1.jpg)
Kruskal（未加刪邊優(yōu)化）：
果/次小生成樹_Kruskal2.jpg)