程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [POJ 1639] 單度限制最小生成樹

[POJ 1639] 單度限制最小生成樹

編輯：C++入門知識

題目大意：

有一個公園，最多只能允許有K條路通向公園，問在這個限制條件下，所能形成的最小生成樹。

資料：

IOI2004國家集訓隊論文--王汀《最小生成樹問題的擴展》

http://wenku.baidu.com/view/41800d66ddccda38376bafac.html

度限制最小生成樹的算法的關鍵是動態規劃來實現更新每一個點到根節點的最大邊。（具體實現見代碼）

/*
ID: [email protected]
PROG:
LANG: C++
度限制最小的生成樹：
1. 去掉根節點，生成一個森林。
2. 將每個子樹分別於根節點相連（取最小的邊）。生成一個m度最小生成樹
3. 迭代(k - m)次，每次連接一條沒用過的與根節點相連的邊，形成一個環，去掉其中不與根節點相連的邊

在更新每一個點到根節點的最大值時，可以采用動態規劃的算法 mx[v] = max(mx[pre[v]], edge[v][pre[v]])
復雜度 O(VlogV + k * n)
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define maxn 105
#define maxm 100005
#define INF (1<<30)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define For(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
using namespace std;
int m, n, head[maxn], cnt, k, vis[maxn];
int cnt_block, ans, belong[maxn], pre[maxn], dis[maxn], use[maxn][maxn], link[maxn], point[maxn];
//cnt_block記錄連通塊的數量，belong[]記錄每個點屬於第幾個連通分量， pre[]記錄生成森林時的前驅， dis[]記錄每個點到該連通分量根節點距離
//use[][]記錄該條邊是否使用，link[]記錄每一連通分量到根節點的最小距離，point[]記錄每個連通分量中與根節點相連的點
vector block[maxn];
map mp;
struct node {
   int v, w, next;
}g[maxm];
struct Edge {
    int u, v, w;
    Edge() {}
    Edge(int a, int b, int c) {
        u = a, v = b, w = c;
    }
    void init() { w = 0; }
    bool operator > (const Edge & a) const {
        return w > a.w;
    }
}mx[maxn];
int getId(char s[]) {
    if (mp.find(s) == mp.end()) mp[s] = ++n;
    else return mp[s];
    return n;
}
void addedge(int u, int v, int w) {
    g[cnt].v = v;
    g[cnt].w = w;
    g[cnt].next = head[u];
    head[u] = cnt++;
}
void dfs(int v) {    //將圖分成若干連通塊
    vis[v] = 1;
    belong[v] = cnt_block;
    block[cnt_block].push_back(v);
    for (int i = head[v]; i != -1; i = g[i].next)
        if (!vis[g[i].v]) dfs(g[i].v);
}
void prim(int cur) {
    dis[block[cur][0]] = 0;
    for (int i = 1; i <= block[cur].size(); i++) {
        int mn = INF, k = -1;
        for (int j = 0; j < block[cur].size(); j++) {
            int v = block[cur][j];
            if (pre[v] != -1 && dis[v] < mn) {
                mn = dis[v];
                k = v;
            }
        }
        if (k != -1) {
            ans += dis[k];
            use[pre[k]][k] = use[k][pre[k]] = 1;
            pre[k] = -1;
            for (int i = head[k]; i != -1; i = g[i].next) if (pre[g[i].v] != -1 && dis[g[i].v] > g[i].w) {
                dis[g[i].v] = g[i].w;
                pre[g[i].v] = k;
            }
        }
    }
}
void MdegreeMST() {
    mem(vis, 0);
    vis[1] = 1;
    cnt_block = 0, ans = 0;
    for (int i = 2; i <= n; i++) if (!vis[i]) {     //求有多少連通分量
        cnt_block++, block[cnt_block].clear();
        dfs(i);
    }

    pre[1] = -1;
    mem(use, 0); mem(pre, 0);
    for (int i = 1; i <= n; i++) dis[i] = link[i] = INF;    //生成最小森林
    for (int i = 1; i <= cnt_block; i++) prim(i);
    for (int i = head[1]; i != -1; i = g[i].next) if (link[belong[g[i].v]] > g[i].w) { //將森林生成一個M度樹
        link[belong[g[i].v]] = g[i].w;
        point[belong[g[i].v]] = g[i].v;
    }
    for (int i = 1; i <= cnt_block; i++) {
        ans += link[i];
        use[1][point[i]] = use[point[i]][1] = 1;
    }
}
void getMax(int v, int fa, int w) {     //更新樹上每一點到根節點的最大距離
    pre[v] = fa;
    Edge tmp(v, fa, w);
    if (tmp > mx[fa]) mx[v] = tmp;
    else mx[v] = mx[fa];
    for (int i = head[v]; i != -1; i = g[i].next) if (use[v][g[i].v] && g[i].v != fa)   //不能產生環路
        getMax(g[i].v, v, g[i].w);
}
void solve() {
    int degree = cnt_block;
    for (int i = 0; i <= n; i++) mx[i].init();
    getMax(1, 0, 0);    //從根節點出發更新每個點到根節點的最大邊
    while (degree < k) {
        int mn = 0, pos = 0, w;
        for (int i = head[1]; i != -1; i = g[i].next) if (!use[1][g[i].v] && mx[g[i].v].w - g[i].w > mn) {
            mn = mx[g[i].v].w - g[i].w;
            pos = g[i].v, w = g[i].w;
        }
        if (!pos) break;
        ans -= mn;
        degree++;
        use[pos][1] = use[1][pos] = 1;
        use[mx[pos].u][mx[pos].v] = use[mx[pos].v][mx[pos].u] = 0;
        getMax(pos, 1, w);
    }
    printf("Total miles driven: %d\n", ans);
}
void init() {
    mem(head, -1);
    cnt = 0, n = 1;
    char s1[55], s2[55];
    scanf("%d", &m);
    mp.clear();
    mp["Park"] = 1;
    int w;
    for (int i = 0; i < m; i++) {
        scanf("%s%s%d", s1, s2, &w);
        int u = getId(s1), v = getId(s2);
        addedge(u, v, w);
        addedge(v, u, w);
    }
    scanf("%d", &k);
}
int main ()
{
    init();
    MdegreeMST();
    solve();
    return 0;
}