給出一個(gè)帶邊權(quán)的無(wú)向圖G，設(shè)其最小生成樹(shù)為T，求出圖G的與T
不完全相同的邊權(quán)和最小的生成樹(shù)（即G的次小生成樹(shù)）。一個(gè)無(wú)向圖的兩棵生成樹(shù)不完全相同，當(dāng)且僅當(dāng)這兩棵樹(shù)中至少有一條邊不同。注意，圖G可能不連通，可能有平行邊，但一定沒(méi)有自環(huán)（其實(shí)對(duì)于自環(huán)也很好處理：直接舍棄。因?yàn)樯蓸?shù)中不可能出現(xiàn)自環(huán)）。
【具體題目】
URAL1416（注意，這一題的邊數(shù)M的范圍沒(méi)有給出，視為124750）
【分析】
定義生成樹(shù)T的一個(gè)可行變換(-E1, +E2)：將T中的邊E1刪除后，再加入邊E2（滿足邊E2原來(lái)不在T中但在G中），若得到的仍然是圖G的一棵生成樹(shù)，則該變換為可行變換，該可行變換的
代價(jià)為(E2權(quán)值 - E1權(quán)值)。這樣，很容易證明，G的次小生成樹(shù)就是由G的最小生成樹(shù)經(jīng)過(guò)一個(gè)代價(jià)最小的可行變換得到。進(jìn)一步可以發(fā)現(xiàn)，
這個(gè)代價(jià)最小的可行變換中加入的邊E2的兩端點(diǎn)如果為V1和V2，那么E1一定是原來(lái)最小生成樹(shù)中從V1到V2的路徑上的權(quán)值最大的邊。
這樣，對(duì)于本題就有兩種算法了：（以下的T全部指G的最小生成樹(shù)）
（1）Prim：
設(shè)立數(shù)組F，F(xiàn)[x][y]表示T中從x到y(tǒng)路徑上的最大邊的權(quán)值。F數(shù)組可以在用Prim算法求最小生成樹(shù)的過(guò)程中得出。每次將邊(i, j)加入后（j是新加入樹(shù)的邊，i=c[j]），枚舉樹(shù)中原有的每個(gè)點(diǎn)k（包括i，但不包括j），則F[k][j]=max{F[k][i], (i, j)邊權(quán)值}，又由于F數(shù)組是對(duì)稱的，可以得到F[j][k]=F[k][j]。然后千萬(wàn)記住將圖G中的邊(i, j)刪除（就是將鄰接矩陣中(i, j)邊權(quán)值改為∞）！因?yàn)門中的邊是不能被加入的。等T被求出后，所有的F值也求出了，然后，枚舉點(diǎn)i、j，若鄰接矩陣中邊(i, j)權(quán)值不是無(wú)窮大（這說(shuō)明i、j間存在不在T中的邊），則求出{(i, j)邊權(quán)值 - F[i][j]}的值，即為加入邊(i, j)的代價(jià)，求最小的總代價(jià)即可。
另外注意三種特殊情況：【1】圖G不連通，此時(shí)最小生成樹(shù)和次小生成樹(shù)均不存在。判定方法：在擴(kuò)展T的過(guò)程中找不到新的可以加入的邊；【2】圖G本身就是一棵樹(shù)，此時(shí)最小生成樹(shù)存在（就是G本身）但次小生成樹(shù)不存在。判定方法：在成功求出T后，發(fā)現(xiàn)鄰接矩陣中的值全部是無(wú)窮大；【3】圖G存在平行邊。這種情況最麻煩，因?yàn)檫@時(shí)代價(jià)最小的可行變換(-E1, +E2)中，E1和E2可能是平行邊！因此，只有建立兩個(gè)鄰接矩陣，分別存儲(chǔ)每?jī)牲c(diǎn)間權(quán)值最小的邊和權(quán)值次小的邊的權(quán)值，然后，每當(dāng)一條新邊(i, j)加入時(shí)，不是將鄰接矩陣中邊(i, j)權(quán)值改為無(wú)窮大，而是改為連接點(diǎ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算法求次小生成樹(shù)的時(shí)空復(fù)雜度均為O(N2)。（2）Kruskal：Kruskal算法也可以用來(lái)求次小生成樹(shù)。在準(zhǔn)備加入一條新邊(a, b)（該邊加入后不會(huì)出現(xiàn)環(huán)）時(shí)，選擇原來(lái)a所在連通塊（設(shè)為S1）與b所在連通塊（設(shè)為S2）中，點(diǎn)的個(gè)數(shù)少的那個(gè)（如果隨便選一個(gè)，最壞情況下可能每次都碰到點(diǎn)數(shù)多的那個(gè)，時(shí)間復(fù)雜度可能增至O(NM)），找到該連通塊中的每個(gè)點(diǎn)i，并遍歷所有與i相關(guān)聯(lián)的邊，若發(fā)現(xiàn)某條邊的另一端點(diǎn)j在未選擇的那個(gè)連通塊中（也就是該邊(i, j)跨越了S1和S2）時(shí)，就說(shuō)明最終在T中"刪除邊(a, b)并加入該邊"一定是一個(gè)可行變換，且由于加邊是按照權(quán)值遞增順序的，(a, b)也一定是T中從i到j(luò)路徑上權(quán)值最大的邊，故這個(gè)可行變換可能成為代價(jià)最小的可行變換，計(jì)算其代價(jià)為[(i, j)邊權(quán)值 - (a, b)邊權(quán)值]，取最小代價(jià)即可。注意，在遍歷時(shí)需要排除一條邊，就是(a, b)本身（具體實(shí)現(xiàn)時(shí)由于用DL邊表，可以將邊(a, b)的編號(hào)代入）。另外還有一個(gè)難搞的地方：如何快速找出某連通塊內(nèi)的所有點(diǎn)？方法：由于使用并查集，連通塊是用樹(shù)的方式存儲(chǔ)的，可以直接建一棵樹(shù)（準(zhǔn)確來(lái)說(shuō)是一個(gè)森林），用“最左子結(jié)點(diǎn)+相鄰結(jié)點(diǎn)”表示，則找出樹(shù)根后遍歷這棵樹(shù)就行了，另外注意在合并連通塊時(shí)也要同時(shí)合并樹(shù)。
對(duì)于三種特殊情況：【1】圖G不連通。判定方法：遍歷完所有的邊后，實(shí)際加入T的邊數(shù)小于(N-1)；【2】圖G本身就是一棵樹(shù)。判定方法：找不到這樣的邊(i, j)；【3】圖G存在平行邊。這個(gè)對(duì)于Kruskal來(lái)說(shuō)完全可以無(wú)視，因?yàn)镵ruskal中兩條邊只要編號(hào)不同就視為不同的邊。
其實(shí)Kruskal算法求次小生成樹(shù)還有一個(gè)優(yōu)化：每次找到邊(i, j)后，一處理完這條邊就把它從圖中刪掉，因?yàn)楫?dāng)S1和S2合并后，(i, j)就永遠(yuǎn)不可能再是可行變換中的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;
}
效率分析：可以證明，如果每次都選取點(diǎn)少的連通塊，Kruskal算法求次小生成樹(shù)的時(shí)間復(fù)雜度為O(M*(logN+logM))，空間復(fù)雜度為O(M)。
總結(jié)：顯然Prim適用于稠密圖，而Kruskal適用于稀疏圖。
下面是對(duì)于一些數(shù)據(jù)的測(cè)試結(jié)果（數(shù)據(jù)說(shuō)明：第1~9個(gè)點(diǎn)和第15個(gè)點(diǎn)為稠密圖或一般圖，第10~14個(gè)點(diǎn)為稀疏圖）
Prim：
評(píng)結(jié)果/次小生成樹(shù)_Prim.jpg)
Kruskal（加入刪邊優(yōu)化）：
評(píng)結(jié)果/次小生成樹(shù)_Kruskal1.jpg)
Kruskal（未加刪邊優(yōu)化）：
評(píng)結(jié)果/次小生成樹(shù)_Kruskal2.jpg)