POJ 1639

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <string>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
// #include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ull, ull> puu;

#define inf (0x3f3f3f3f)
#define lnf (0x3f3f3f3f3f3f3f3f)
#define eps (1e-9)
#define fi first
#define se second

bool sgn(double a, string select, double b) {
    if(select == "==")return fabs(a - b) < eps;
    if(select == "!=")return fabs(a - b) > eps;
    if(select == "<")return a - b < -eps;
    if(select == "<=")return a - b < eps;
    if(select == ">")return a - b > eps;
    if(select == ">=")return a - b > -eps;
}


//--------------------------

const ll mod = 1000000007;
const int maxn = 30;

struct Edge {
    int u, v, d;
    Edge() {}
    Edge(int a, int b, int c): u(a), v(b), d(c) {}
    bool operator<(const Edge &e)const {
        return d < e.d;
    }
};

int n, m, k;
int cnt;
int ans;
int parent[maxn];
map<string, int> nodes;
vector<Edge>edges;
int g[maxn][maxn];
bool tree[maxn][maxn];
int minEdge[maxn];
Edge dp[maxn];

int find(int p) {
    if(p == parent[p])return p;
    else return parent[p] = find(parent[p]);
}

void un(int p, int q) {
    parent[find(p)] = find(q);
}

void Kruskal() {
    sort(edges.begin(), edges.end());
    for(int i = 0; i < edges.size(); i++) {
        int p = edges[i].u;
        int q = edges[i].v;
        if(p == 1 || q == 1)continue;
        if(find(p) != find(q)) {
            un(p, q);
            tree[p][q] = tree[q][p] = 1;
            ans += edges[i].d;
        }
    }
}

void dfs(int cur, int pre) {
    for(int i = 2; i <= cnt; i++) {
        if(i == pre || !tree[cur][i])continue;
        if(dp[i].d == -1) {
            if(dp[cur].d > g[cur][i])dp[i] = dp[cur];
            else {
                dp[i].u = cur;
                dp[i].v = i;
                dp[i].d = g[cur][i];
            }
        }
        dfs(i, cur);
    }
}


void init() {
    memset(g, inf, sizeof(g));
    memset(tree, 0, sizeof(tree));
    memset(minEdge, inf, sizeof(minEdge));
    m = 0;
    cnt = 1;
    ans = 0;
    nodes["Park"] = 1;
    for(int i = 0; i < maxn; i++) {
        parent[i] = i;
    }
}

void solve() {
    scanf("%d", &n);
    string s1, s2;
    int d;
    init();
    for(int i = 1; i <= n; i++) {
        cin >> s1 >> s2 >> d;
        if(!nodes[s1])nodes[s1] = ++cnt;
        if(!nodes[s2])nodes[s2] = ++cnt;
        int u = nodes[s1];
        int v = nodes[s2];
        edges.push_back(Edge(u, v, d));
        g[u][v] = g[v][u] = min(g[u][v], d);
    }
    scanf("%d", &k);
    Kruskal();
    int keyPoint[maxn];
    for(int i = 2; i <= cnt; i++) {
        if(g[1][i] != inf) {
            int color = find(i);
            if(minEdge[color] > g[1][i]) {
                minEdge[color] = g[1][i];
                keyPoint[color] = i;

            }
        }
    }
    for(int i = 1; i <= cnt; i++) {
        if(minEdge[i] != inf) {
            m++;
            tree[1][keyPoint[i]] = tree[keyPoint[i]][1] = 1;
            ans += g[1][keyPoint[i]];
        }
    }
    for(int i = m + 1; i <= k; i++) {
        memset(dp, -1, sizeof(dp));
        dp[1].d = -inf;
        for(int j = 2; j <= cnt; j++)
            if(tree[1][j])
                dp[j].d = -inf;
        dfs(1, -1);
        int idx, minnum = inf;
        for(int j = 2; j <= cnt; j++) {
            if(minnum > g[1][j] - dp[j].d) {
                minnum = g[1][j] - dp[j].d;
                idx = j;
            }
        }
        if(minnum >= 0)
            break;
        tree[1][idx] = tree[idx][1] = 1;
        tree[dp[idx].u][dp[idx].v] = tree[dp[idx].v][dp[idx].u] = 0;
        ans += minnum;
    }
    printf("Total miles driven: %d\n", ans);
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
#endif
    // iostream::sync_with_stdio(false);
    solve();
    return 0;
}