最小生成树

本来想好好写的....连续电脑挂了3次....就转载一篇了....

先看一个结论：次小生成树可由最小生成树换一条边得到

         证明:咱换种方式去看待这个结论(一个生成树可以通过换边得到另一个生成树)，T是某一棵最小生成树，T0是任一棵异于T的生成树，通过变换T0 --> T1 --> T2 --> ... --> Tn (T)  变成最小生成树。所谓的变换是，每次把Ti中的某条边换成T中的一条边, 而且树T(i+1)的权小于等于Ti的权。

         看下面的具体步骤(一定要理解透彻)。 
         step 1. 在Ti中任取一条不在T中的边uv. 
         step 2. 把边uv去掉，就剩下两个连通分量A和B，在T中，必有唯一的边u'v' 连结A和B。这是为什么呢？因为生成树中任意两点间只有一条路径(下面也要用这个)，且必有一条。 
         step 3. 显然u'v'的权比uv小 (prime算法贪心的，否则,uv就应该在T中)，把u'v'替换uv即得树T(i+1)。 
         特别地：取T0为任一棵次小生成树，T(n-1) 也就是次小生成树且跟T差一条边， 结论得证。

方法是：

1、找到最小生成树，值为mst

2、最小生成树种的点：找到每一个点到其它点的路径上的最大边权值 dp[i][j]表示i到j路径上的最大边权值

3、加一条不在最小生成树上的边。比如i - k，同时删除在最小生成树上i -> k路径上最大的一个边权值dp[i][k]; 这样会得到 new_mst，在这些new_mst中找一个最小的，就是次小生成树的值

实现上用到一些技巧，代码如下POJ 1679：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <ctime>
#include <queue>
#include <map>
#include <sstream>


#define CL(arr, val)    memset(arr, val, sizeof(arr))
#define REP(i, n)       for((i) = 0; (i) < (n); ++(i))
#define FOR(i, l, h)    for((i) = (l); (i) <= (h); ++(i))
#define FORD(i, h, l)   for((i) = (h); (i) >= (l); --(i))
#define L(x)    (x) << 1
#define R(x)    (x) << 1 | 1
#define MID(l, r)   (l + r) >> 1
#define Min(x, y)   x < y ? x : y
#define Max(x, y)   x < y ? y : x
#define E(x)    (1 << (x))


const int eps = 1e-6;
const int inf = ~0u>>2;
typedef long long LL;


using namespace std;


const int N = 110;
const int M = 100000;


struct node {
    int to;
    int next;
} G[M];


int mp[N][N];
int dis[N];
int pre[N];
bool vis[N];


int head[N], t;
int n;


bool inMST[N][N];
int dp[N][N];


void add(int u, int v) {
    G[t].to = v; G[t].next = head[u]; head[u] = t++;
}


int prim() {
    int i, j, f, mx, ret = 0;
    for(i = 1; i <= n; ++i)   {
        dis[i] = inf;
        pre[i] = 0;
        vis[i] = false;
    }
    pre[1] = 0;
    dis[1] = 0;
    for(i = 1; i <= n; ++i) {
        mx = inf; f = 0;
        for(j = 1; j <= n; ++j) {
            if(!vis[j] && mx > dis[j]) {
                mx = dis[j];
                f = j;
            }
        }
        vis[f] = true;
        ret += mx;
        for(j = 1; j <= n; ++j) {
            if(!vis[j] && dis[j] > mp[f][j]) {
                pre[j] = f;
                dis[j] = mp[f][j];
            }
        }
    }
    for(i = 1; i <= n; ++i) {   //记录在最小生成树上的边
        if(pre[i]) inMST[pre[i]][i] = inMST[i][pre[i]] = true;
    }


    for(i = 1; i <= n; ++i) {    //建新图，用来找在最小生成树上 i->j路径中最大的一个边权值
        if(pre[i])  {add(pre[i], i); add(i, pre[i]); }
        //printf("%d %d ", i , pre[i]);
    }
    return ret;
}


void init() {
    int i, j;
    for(i = 1; i <= n; ++i) {
        for(j = 1; j <= n; ++j) {
            mp[i][j] = (i == j ? 0 : inf);
        }
    }
    CL(head, -1); t = 0;
    CL(inMST, false);
    CL(dp, 0);
}


void dfs(int st, int to, int val) {    //。。。
    vis[to] = true;
    dp[st][to] = val;
    for(int i = head[to]; i != -1; i = G[i].next) {
        if(!vis[G[i].to])
            dfs(st, G[i].to, max(val, mp[to][G[i].to]));
    }
}


int main() {
    //freopen("data.in", "r", stdin);


    int t, m, i, j;
    int u, v, w;
    int ans, mst;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &m);
        init();
        while(m--) {
            scanf("%d%d%d", &u, &v, &w);
            mp[u][v] = mp[v][u] = w;
        }


        mst = prim(); ans = inf;
        for(i = 1; i <= n; ++i) {
            CL(vis, false);
            dfs(i, i, 0);
        }


        for(i = 1; i <= n; ++i) {
            for(j = i + 1; j <= n; ++j) {
                if(!inMST[i][j] && mp[i][j] != inf)    //加边
                    ans = min(ans, mst - dp[i][j] + mp[i][j]);
            }
        }
        if(ans == mst)  puts("Not Unique!");
        else    printf("%d ", mst);
    }
    return 0;
}