UVA 10600 ACM Contest and Blackout(Second MST)

Description

N个点M条边，求最小生成树与次小生成树

（求生成树，说明边是无向边）

Analyze

设原图G(V, E)，最小生成树T(V1, E1)，现有边(u, v)∈G && (u, v)∉T。u与v之间有唯一的一条路径，将这条路上若干段中最长的一段的长度存储在len[u][v]里，将边(u, v)加入到T中，u与v间形成了环，删掉len[u][v]对应那条边就是一颗准次小生成树了。

遍历所有的非最小生成树内的边，求出相应的一个个准次小生成树，这里面最小的一个就是真正的次小生成树了。

len[u][v]求解

Prim：类似于DP的方法len[i][pos] = len[pos][i] = max(len[i][pre[pos]], low[pos]);

Kruskal：有先天优势(边是按权值从小到大排序的，即：当前边的权值是当前已经出现的所有边中的最大值，此时用当前的边将两个集合连接，两集合内各取一点，他们之间路径上最大边就是当前边)len[ G[aa][i] ][ G[bb][j] ] = len[ G[bb][j] ][ G[aa][i] ] = w;

Code of Prim

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 105;

int n, m, MST, SecondMST;
int mp[N][N], len[N][N], pre[N], low[N];
bool vis[N], used[N][N];

int Prim()
{
    int ans = 0;
    memset(len, 0, sizeof(len));
    memset(vis, 0, sizeof(vis));
    memset(used, 0, sizeof(used));

    ans += 0, vis[1] = 1;
    for(int i = 1; i <= n; ++i)
    {
        low[i] = mp[i][1];
        pre[i] = 1;
    }

    int cnt = n, mmin = INF, pos = 1;
    while(--cnt)
    {
        mmin = INF;
        for(int i = 1; i <= n; ++i)
            if(!vis[i] && low[i] < mmin)
                mmin = low[i], pos = i;

        ///if(mmin == INF)

        ans += mmin, vis[pos] = 1;
        used[pos][pre[pos]] = used[pre[pos]][pos] = 1;
        for(int i = 1; i <= n; ++i)
        {
            if(vis[i] && i != pos)
                len[i][pos] = len[pos][i] = max(len[i][pre[pos]], low[pos]);
            if(!vis[i] && low[i] > mp[pos][i])
                low[i] = mp[pos][i], pre[i] = pos;
        }
    }
    return ans;
}

int SecondPrim()
{
    int ans = INF;
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j)
            if(!used[i][j] && mp[i][j] != INF)
                ans = min(ans, MST + mp[i][j] - len[i][j]);
    return ans;
}

int main()
{
    int _;
    scanf("%d", &_);
    while(_--)
    {
        scanf("%d %d", &n, &m);
        for(int i = 0; i <= n; ++i)
            for(int j = 0; j <= n; ++j)
                mp[i][j] = mp[j][i] = (i == j ? 0 : INF);
        int u, v, w;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d %d %d", &u, &v, &w);
            mp[u][v] = mp[v][u] = w;
        }
        MST = Prim();
        SecondMST = SecondPrim();
        cout << MST << ' ' << SecondMST << '\n';
    }
    return 0;
}

Code of Kruskal

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 105;

int n, m, MST, SecondMST, pre[N], len[N][N];
vector<int> G[N];

int cnt;
struct edge
{
    int there, here, w, vis;
    bool operator < (edge & t)const
    {
        return w < t.w;
    }
} e[N * N];

int found(int x)
{
    return pre[x] == -1 ? x : pre[x] = found(pre[x]);
}

int unite(int a, int b, int w)
{
    int aa = found(a);
    int bb = found(b);
    if(aa != bb)
    {
        int asz = G[aa].size();
        int bsz = G[bb].size();
        for(int i = 0; i < asz; ++i)
            for(int j = 0; j < bsz; ++j)
                len[ G[aa][i] ][ G[bb][j] ] = len[ G[bb][j] ][ G[aa][i] ] = w;
        pre[aa] = bb;
        for(int i = 0; i < asz; ++i)
            G[bb].push_back(G[aa][i]);
        return 1;
    }
    return 0;
}

int Kruskal()
{
    memset(pre, -1, sizeof(pre));
    memset(len,  0, sizeof(len));
    for(int i = 0; i <= n; ++i)
        G[i].clear(), G[i].push_back(i);

    int ans = 0, tot = 0;
    sort(e, e + cnt);
    for(int i = 0; i < cnt; ++i)
    {
        if(tot == n - 1)
            break;
        e[i].vis = unite(e[i].there, e[i].here, e[i].w);
        ans += e[i].vis * e[i].w, tot += e[i].vis;
    }
    return ans;
}

int SecondKruskal()
{
    int ans = INF;
    for(int i = 0; i < m; ++i)
        if(!e[i].vis)
            ans = min(ans, MST + e[i].w - len[ e[i].there ][ e[i].here ]);
    return ans;
}

int main()
{
    int _;
    scanf("%d", &_);
    while(_--)
    {
        cnt = 0;
        scanf("%d %d", &n, &m);
        for(int i = 0; i < m; ++i)
        {
            scanf("%d %d %d", &e[cnt].there, &e[cnt].here, &e[cnt].w);
            e[cnt++].vis = 0;
        }
        MST = Kruskal();
        SecondMST = SecondKruskal();
        cout << MST << ' ' << SecondMST << '\n';
    }
    return 0;
}