题目描述

一群小丑演员，以其出色的柔术表演，可以无限量的钻进同一辆汽车中，而闻名世界。

现在他们想要去公园玩耍，但是他们的经费非常紧缺。

他们将乘车前往公园，为了减少花费，他们决定选择一种合理的乘车方式，可以使得他们去往公园需要的所有汽车行驶的总公里数最少。

为此，他们愿意通过很多人挤在同一辆车的方式，来减少汽车行驶的总花销。

由此，他们可以很多人驾车到某一个兄弟的家里，然后所有人都钻进一辆车里，再继续前进。

公园的停车场能停放的车的数量有限，而且因为公园有入场费，所以一旦一辆车子进入到公园内，就必须停在那里，不能再去接其他人。

现在请你想出一种方法，可以使得他们全都到达公园的情况下，所有汽车行驶的总路程最少。

输入格式
第一行包含整数n，表示人和人之间或人和公园之间的道路的总数量。

接下来n行，每行包含两个字符串A、B和一个整数L，用以描述人A和人B之前存在道路，路长为L，或者描述某人和公园之间存在道路，路长为L。

道路都是双向的，并且人数不超过20，表示人的名字的字符串长度不超过10，公园用“Park”表示。

再接下来一行，包含整数s，表示公园的最大停车数量。

你可以假设每个人的家都有一条通往公园的道路。

输出格式
输出“Total miles driven: xxx”，其中xxx表示所有汽车行驶的总路程。

算法

看书上解法 写了好几小时orz 细节蛮多的
看网上都没有前向星存的 来发一篇blog
复杂度 nlogn 起步 最情况复杂n^2

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 5;
int n, m;
map<string, int> id;
map<pair<int, int>, bool> e_vis;

int head[maxn], milu[maxn], path[maxn], cnt, idx;
int to[maxn << 1], nxt[maxn << 1], dis[maxn << 1];

void ade(int a, int b, int c) {
    to[++cnt] = b;
    dis[cnt] = c;
    nxt[cnt] = head[a];
    head[a] = cnt;
}

int cmp[maxn], scc_col;

void dfs(int u) {
    cmp[u] = scc_col;
    for(int i = head[u]; i; i = nxt[i]) {
        if(cmp[to[i]]) continue;
        if(to[i] == 1) continue;
        dfs(to[i]);
    }
}

struct node {
    int x, y;
    int z;
    bool operator < (const node & a) const {
        return z < a.z;
    }
} que[maxn];
int hh, tt;

bool vis[maxn];
int pre[maxn];
void init() {
    for(int i = 0; i <maxn; i ++ ) pre[i] = i;
}

int finds(int x) {
    return pre[x] == x ? x : pre[x] = finds(pre[x]);
}

void unions(int x, int y) {
    x = finds(x), y =finds(y);
    pre[x] = y;
}

int kruskal() {
    int res = 0;
    sort(que + hh, que + tt + 1);
    init();
    for(int i = hh, x, y; i < tt; i ++) {   

        x = finds(que[i].x), y = finds(que[i].y);
        if(x != y) {
//  cout << que[i].x << " " << que[i].y << "  " << que[i].z << endl;
        e_vis[make_pair(que[i].x, que[i].y)] = 1;
        e_vis[make_pair(que[i].y, que[i].x)] = 1;
            res += que[i].z;
            unions(x, y);
        }
    }
    return res;
}

void dfs(int u, int pre) {
    for(int i = head[u]; i; i = nxt[i]){
        int v = to[i];
        if(v == pre || !e_vis[make_pair(u, v)]) continue;
        if(que[v].z < que[u].z) que[v] = que[u];
        if(que[v].z < dis[v]) {
            que[v].x = u;
            que[v].y = v;
            que[v].z = dis[i];
        }
        dfs(v, u);
    }
}

int main() {
    id["Park"] = 1;
    idx = 1;
    cin >> n;
    for(int i = 1, d; i <= n; i ++ ) {
        string s1, s2;
        cin >> s1 >> s2 >> d;
        if(!id[s1]) id[s1] = ++idx;
        if(!id[s2]) id[s2] = ++idx;
        ade(id[s1], id[s2], d), ade(id[s2], id[s1], d);
    }
    //cout << idx << endl;
    cin >> m;
    for(int i = 2; i <= idx; i ++)
        if(!cmp[i]) ++scc_col, dfs(i);

//  cout << scc_col << endl;

    if(scc_col > m) {
        cout << -1 << endl;
    } else {
        int ans = 0;
        for(int col = 1; col <= scc_col; col ++ ) {
            int mito1 = 0x3f3f3f3f;
            hh = 1, tt = 1;
            for(int u = 1; u <= n; u ++ ) {
                if(col != cmp[u]) continue;
                for(int i = head[u]; i; i = nxt[i]) {
                    if(col == cmp[to[i]]) {
                        vis[to[i]] = 1;
                        que[tt++] = node {u, to[i], dis[i]};
                    }
                }
            }
            ans += kruskal();
        }
    //  cout << ans << endl;

        memset(milu, 0x3f, sizeof milu);
        for(int i = head[1]; i; i =nxt[i]) {
            if(milu[cmp[to[i]]] > dis[i]) {
                milu[cmp[to[i]]] = dis[i];
                path[cmp[to[i]]] = to[i];
            }
        }

        for(int i = 1; i <= scc_col; i ++ ){
            e_vis[make_pair(1, path[i])] = 1;
            e_vis[make_pair(path[i], 1)] = 1;
            ans += milu[i];
        } 

    //  cout << ans << endl;

        int s = m - scc_col;
        while(s--) {
            memset(que, -1, sizeof(que));
            dfs(1, -1);
//          cout << " ----------" << endl;
//          for(int i = 1; i <= idx; i ++ ) {
//              cout << i << ":  " << endl;
//              cout << que[i].x << " " << que[i].y << " " << que[i].z << endl;
//          }       
            int w = 0, pos = 0;
            for(int i = head[1]; i; i = nxt[i] ) {
            //  cout << w << " " << que[to[i]].z << "  " << dis[i] << endl;
                if(w <= que[to[i]].z - dis[i]) {
                    w = que[to[i]].z - dis[i];
                    pos = to[i];
                }
            }
//          cout << que[pos].x << "  " << que[pos].y << " " << que[pos].z << endl;
//          cout << pos << endl;
//          cout << w << endl;
//          getchar();



            if(w < 0) break;
            ans -= w;       
            e_vis[make_pair(1, pos)] = e_vis[make_pair(pos, 1)] = 1;
            e_vis[make_pair(que[pos].x, que[pos].y)] = 0;
            e_vis[make_pair(que[pos].y, que[pos].x)] = 0;
        }

        cout << "Total miles driven: " << ans <<endl;
    }
    return 0;
}

/*
11
Park Bill 3
Park Jane 2
Park Todd 1
Todd Jane 5
Bill Todd 1
Bill John 5
Bill Emma 2
John Jane 1
Emma Jane 3
Emma John 8
Bill Jane 7
2
*/