Picnic Planning

题目描述

The Contortion Brothers are a famous set of circus clowns, known worldwide for their incredible ability to cram an unlimited number of themselves into even the smallest vehicle. During the off-season, the brothers like to get together for an Annual Contortionists Meeting at a local park. However, the brothers are not only tight with regard to cramped quarters, but with money as well, so they try to find the way to get everyone to the party which minimizes the number of miles put on everyone’s cars (thus saving gas, wear and tear, etc.). To this end they are willing to cram themselves into as few cars as necessary to minimize the total number of miles put on all their cars together. This often results in many brothers driving to one brother’s house, leaving all but one car there and piling into the remaining one. There is a constraint at the park, however: the parking lot at the picnic site can only hold a limited number of cars, so that must be factored into the overall miserly calculation. Also, due to an entrance fee to the park, once any brother’s car arrives at the park it is there to stay; he will not drop off his passengers and then leave to pick up other brothers. Now for your average circus clan, solving this problem is a challenge, so it is left to you to write a program to solve their milage minimization problem.

题意概述

给定一张$N$个点的带权无向图，求一棵生成树使得$0$号点的度数不超过$K$，且边权之和最小。

数据范围：$1 \le N \le 21$。

算法分析

这是经典的最小度限制生成树问题。算法如下：

1. 先算出不包含$0$号点的最小生成森林，对于森林中的每一棵树，选一条权值最小的边与$0$号点相连；
2. 设此时$0$号点的度数为$M$；若$M$大于$K$，则无解；
3. 以$0$号点为树的根，计算出每个点到根的路径上不与根相连的边的权值的最大值$w_i$以及其对应的边$(u_i, v_i)$；
4. 令$d_{i, j}$表示$i, j$之间直接相连的边的权值。枚举与$0$号点之间有边但在树上不直接相连的点，计算出$d_{0, i}-w_i$的最小值$mn$；
5. 若$mn \ge 0$，则退出；否则，在树中加入边$(0, i)$，并删去边$(u_i, v_i)$，令$M$加$1$；
6. 若$M=K$，则退出；否则，返回 3。

代码

#include <map>
#include <cstring>
#include <iostream>
#include <algorithm>

int cnt = 1, fa[25], mp[25][25], ori[25][25], mx[25];
std :: pair <int, int> rec[25];
struct Line {
  int u, v, d;
  bool operator < (const Line &l) const {
    return d < l.d;
  }
} l[450];
std :: map <std :: string, int> name;

int get_fa(int t) {
  return t == fa[t] ? t : fa[t] = get_fa(fa[t]);
}

void dfs(int t, int fa) {
  for (int i = 0; i < cnt; ++ i)
    if (~ mp[t][i] && i != fa) {
      mx[i] = mx[t], rec[i] = rec[t];
      if (mp[t][i] > mx[t]) mx[i] = mp[t][i], rec[i] = std :: make_pair(t, i);
      dfs(i, t);
    }
}

void calc() {
  memset(mx, -1, sizeof mx);
  for (int i = 0; i < cnt; ++ i) if (~ mp[0][i]) dfs(i, 0);
}

int main() {
  int n; std :: cin >> n, name["Park"] = 0;
  memset(ori, -1, sizeof ori);
  for (int i = 0; i < n; ++ i) {
    std :: string u, v; int d; std :: cin >> u >> v >> d;
    if (! name.count(u)) name[u] = cnt ++;
    if (! name.count(v)) name[v] = cnt ++;
    l[i] = (Line) { name[u], name[v], d };
    if (l[i].u > l[i].v) std :: swap(l[i].u, l[i].v);
    if (! ~ ori[l[i].u][l[i].v]) ori[l[i].u][l[i].v] = ori[l[i].v][l[i].u] = d;
    else ori[l[i].u][l[i].v] = ori[l[i].v][l[i].u] = std :: min(ori[l[i].u][l[i].v], d);
  }
  int m = 0; std :: sort(l, l + n);
  for (int i = 0; i < cnt; ++ i) fa[i] = i;
  memset(mp, -1, sizeof mp);
  for (int i = 0; i < n; ++ i)
    if (l[i].u) {
      int p = get_fa(l[i].u), q = get_fa(l[i].v);
      if (p != q) fa[p] = q, mp[l[i].u][l[i].v] = mp[l[i].v][l[i].u] = l[i].d;
    }
  for (int i = 0; i < n; ++ i)
    if (! l[i].u) {
      int p = get_fa(l[i].u), q = get_fa(l[i].v);
      if (p != q) fa[p] = q, ++ m, mp[l[i].u][l[i].v] = mp[l[i].v][l[i].u] = l[i].d;
    }
  int k; std :: cin >> k;
  while (m < k) {
    calc();
    int mn = 1e9, p = -1;
    for (int i = 0; i < cnt; ++ i)
      if (~ ori[0][i] && ! ~ mp[0][i] && ~ mx[i] && ori[0][i] - mx[i] < mn) mn = ori[0][i] - mx[i], p = i;
    if (mn >= 0) break;
    mp[0][p] = mp[p][0] = ori[0][p];
    mp[rec[p].first][rec[p].second] = mp[rec[p].second][rec[p].first] = -1;
    ++ m;
  }
  int ans = 0;
  for (int i = 0; i < cnt; ++ i)
    for (int j = 0; j < i; ++ j) if (~ mp[i][j]) ans += mp[i][j];
  std :: cout << "Total miles driven: " << ans << std :: endl;
  return 0;
}