Desert King

题目描述

David the Great has just become the king of a desert country. To win the respect of his people, he decided to build channels all over his country to bring water to every village. Villages which are connected to his capital village will be watered. As the dominate ruler and the symbol of wisdom in the country, he needs to build the channels in a most elegant way.
After days of study, he finally figured his plan out. He wanted the average cost of each mile of the channels to be minimized. In other words, the ratio of the overall cost of the channels to the total length must be minimized. He just needs to build the necessary channels to bring water to all the villages, which means there will be only one way to connect each village to the capital.
His engineers surveyed the country and recorded the position and altitude of each village. All the channels must go straight between two villages and be built horizontally. Since every two villages are at different altitudes, they concluded that each channel between two villages needed a vertical water lifter, which can lift water up or let water flow down. The length of the channel is the horizontal distance between the two villages. The cost of the channel is the height of the lifter. You should notice that each village is at a different altitude, and different channels can’t share a lifter. Channels can intersect safely and no three villages are on the same line.
As King David’s prime scientist and programmer, you are asked to find out the best solution to build the channels.

题意概述

空间中有$N$个点。定义点$(x_0, y_0, z_0)$与点$(x_1, y_1, z_1)$之间的距离为$\sqrt{(x_0-x_1)^2+(y_0-y_1)^2}$,在它们之间连边的花费为$|z_0-z_1|$。要使得任意两点之间恰有一条路径,求总花费除以总距离的最小值。
数据范围:$2 \le N \le 1000$。

算法分析

假设我们连边的集合为$S$,最小值为$k$。令$l_i$表示边的长度,$c_i$表示边的花费。那么有
$$
{\sum_{i \in S} c_i \over \sum_{i \in S} l_i} \ge k
$$
移项得
$$
\begin{align}
\sum_{i \in S} c_i &\ge k\sum_{i \in S} l_i \\
\sum_{i \in S} (c_i-kl_i) &\ge 0
\end{align}
$$
不管怎么连边,这个不等式都成立。因此只要可以判断是否存在不满足不等式的连边方案,就可以对$k$进行二分。我们给每条边$i$赋权$c_i-kl_i$,那显然最坏情况就是新图的最小生成树。
还有一种基于迭代的方法。在求出最小生成树后,将$k$赋值为这棵最小生成树的总花费除以总距离,继续迭代,直到满足精度要求为止。
最小生成树需要用Prim来求,否则容易超时。

代码

/*
 * Good news from afar can bring you a welcome visitor.
 */

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

#define sqr(x) (1. * (x) * (x))

static int const N = 1005;
static double const EPS = 1e-5;
int fa[N], vis[N], pre[N];
double dist[N], mp[N][N];
struct Point {
  int x, y, z;
} p[N];

int main() {
  int n;
  for (scanf("%d", &n); n; scanf("%d", &n)) {
    for (int i = 1; i <= n; ++i)
      scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);
    double ans = 0;
    for (;;) {
      for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
          if (i != j)
            mp[i][j] = abs(p[i].z - p[j].z) -
                       ans * sqrt(sqr(p[i].x - p[j].x) + sqr(p[i].y - p[j].y));
      double cost = 0, len = 0;
      memset(vis, 0, sizeof vis), vis[1] = 1;
      for (int i = 2; i <= n; ++i)
        dist[i] = mp[1][i], pre[i] = 1;
      for (int i = 2; i <= n; ++i) {
        int pos = 0;
        double mn = 1e15;
        for (int j = 1; j <= n; ++j)
          if (!vis[j] && dist[j] < mn)
            mn = dist[pos = j];
        vis[pos] = 1, cost += abs(p[pos].z - p[pre[pos]].z),
        len +=
            sqrt(sqr(p[pos].x - p[pre[pos]].x) + sqr(p[pos].y - p[pre[pos]].y));
        for (int j = 1; j <= n; ++j)
          if (!vis[j] && mp[pos][j] < dist[j])
            dist[j] = mp[pos][j], pre[j] = pos;
      }
      if (abs(cost / len - ans) < EPS) {
        printf("%.3lf\n", ans);
        break;
      }
      ans = cost / len;
    }
  }
  return 0;
}

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;
}

Best Edge Weight

题目描述

You are given a connected weighted graph with $n$ vertices and $m$ edges. The graph doesn’t contain loops nor multiple edges. Consider some edge with id $i$. Let’s determine for this edge the maximum integer weight we can give to it so that it is contained in all minimum spanning trees of the graph if we don’t change the other weights.
You are to determine this maximum weight described above for each edge. You should calculate the answer for each edge independently, it means there can’t be two edges with changed weights at the same time.

题意概述

给定一张$n$个点$m$条边的连通无向图,边权均为正数。对于每一条边,询问它的边权至多是多少,使得在其他边权不变的条件下,它在这张图的所有最小生成树中。
数据范围:$2 \le n \le 2 \times 10^5, \; n-1 \le m \le 2 \times 10^5$。

算法分析

题目要求一条边在所有最小生成树中。我们无法求出所有最小生成树,因此先求出其中一棵。这样,图中的边就被分成了两种:一种在这棵最小生成树中,另一种不在这棵最小生成树中。
对于不在这棵最小生成树中的边$(u, v)$,设它的权值为$w$。显然,它和最小生成树上从$u$到$v$的路径构成了一个环。设这条路径上边权的最大值$w_{max}$。如果$w \ge w_{max}$,那么$(u, v)$可能在这张图的一棵最小生成树中,但一定不是所有。因此,可以将$w$设成$w_{max}-1$,因为根据贪心策略,将路径上权值为$w_{max}$的边替换成$(u, v)$,会得到一棵更小的生成树。这种情况很好解决,只要在最小生成树上进行倍增就可以了。
对于在这棵最小生成树中的边$(u, v)$,设它的权值为$w$。假设我们找到了一条不经过这棵最小生成树上的边从$u$到$v$的路径,设这条路径上边权的最小值为$w_{min}$。类似于不在最小生成树的边,如果$w \ge w_{min}$,那么这条边一定不在所有最小生成树中。将它的权值设为$w_{min}-1$,即可满足要求。由于直接求$w_{min}$较为困难,因此可以按边权从小到大枚举不在这棵最小生成树中的边,并用它来更新最小生成树上的一条路径。因为是从小到大枚举,所以最小生成树上的每条边只需要被更新一次,可以用并查集维护。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct line {
  long long u, v, c, id; bool mst;
  bool operator < (const line &a) const { return c < a.c; }
} l[200001];
struct edge {
  long long v, c, id, nxt;
} e[400001];
long long n, m, nume, h[200001], fa[200001], ans[200001];
long long depth[200001], up[200001][20], ma[200001][20], uid[200001];
long long get_fa(long long t) { return t == fa[t] ? t : fa[t] = get_fa(fa[t]); }
void add_edge(long long u, long long v, long long c, long long id) {
  e[++nume].v = v, e[nume].c = c, e[nume].id = id, e[nume].nxt = h[u], h[u] = nume;
  e[++nume].v = u, e[nume].c = c, e[nume].id = id, e[nume].nxt = h[v], h[v] = nume;
}
void dfs(long long t, long long fa) {
  for (int i = h[t]; i; i = e[i].nxt)
    if (e[i].v != fa) {
      depth[e[i].v] = depth[t] + 1, up[e[i].v][0] = t;
      ma[e[i].v][0] = e[i].c, uid[e[i].v] = e[i].id, dfs(e[i].v, t);
    }
}
long long get_max(long long u, long long v) {
  long long ret = 0;
  if (depth[u] < depth[v]) u ^= v ^= u ^= v;
  for (int i = 19; i >= 0; --i)
    if (depth[u] - depth[v] >= (1 << i))
      ret = max(ret, ma[u][i]), u = up[u][i];
  if (u == v) return ret;
  for (int i = 19; i >= 0; --i)
    if (up[u][i] != up[v][i])
      ret = max(ret, max(ma[u][i], ma[v][i])), u = up[u][i], v = up[v][i];
  return max(ret, max(ma[u][0], ma[v][0]));
}
void update(long long u, long long v, long long val) {
  if (depth[u] < depth[v]) u ^= v ^= u ^= v;
  long long p = u, q = v;
  for (int i = 19; i >= 0; --i)
    if (depth[p] - depth[q] >= (1 << i)) p = up[p][i];
  if (p != q) {
    for (int i = 19; i >= 0; --i)
      if (up[p][i] != up[q][i]) p = up[p][i], q = up[q][i];
    p = up[p][0];
  }
  u = get_fa(u), v = get_fa(v);
  while (depth[u] > depth[p])
    ans[uid[u]] = val - 1, q = get_fa(up[u][0]), fa[u] = q, u = get_fa(u);
  while (depth[v] > depth[p])
    ans[uid[v]] = val - 1, q = get_fa(up[v][0]), fa[v] = q, v = get_fa(v);
}
int main()
{
  cin >> n >> m, memset(ans, -1, sizeof ans);
  if (n == m + 1) {
    for (int i = 1; i <= m; cout << -1 << ' ', ++i); cout << endl; return 0;
  }
  for (int i = 1; i <= n; fa[i] = i, ++i);
  for (int i = 1; i <= m; cin >> l[i].u >> l[i].v >> l[i].c, l[i].id = i, ++i);
  sort(l + 1, l + m + 1);
  for (int i = 1; i <= m; ++i) {
    long long u = get_fa(l[i].u), v = get_fa(l[i].v);
    if (u != v) add_edge(l[i].u, l[i].v, l[i].c, l[i].id), fa[u] = v, l[i].mst = true;
  }
  depth[1] = 1, dfs(1, 0);
  for (int i = 1; i < 20; ++i)
    for (int j = 1; j <= n; ++j) {
      up[j][i] = up[up[j][i - 1]][i - 1];
      ma[j][i] = max(ma[j][i - 1], ma[up[j][i - 1]][i - 1]);
    }
  for (int i = 1; i <= n; fa[i] = i, ++i);
  for (int i = 1; i <= m; ++i)
    if (!l[i].mst) {
      ans[l[i].id] = get_max(l[i].u, l[i].v) - 1;
      update(l[i].u, l[i].v, l[i].c);
    }
  for (int i = 1; i <= m; cout << ans[i] << ' ', ++i);
  cout << endl;
  return 0;
}

Opening Portals

题目描述

Pavel plays a famous computer game. A player is responsible for a whole country and he can travel there freely, complete quests and earn experience.
This country has $n$ cities connected by $m$ bidirectional roads of different lengths so that it is possible to get from any city to any other one. There are portals in $k$ of these cities. At the beginning of the game all portals are closed. When a player visits a portal city, the portal opens. Strange as it is, one can teleport from an open portal to an open one. The teleportation takes no time and that enables the player to travel quickly between rather remote regions of the country.
At the beginning of the game Pavel is in city number $1$. He wants to open all portals as quickly as possible. How much time will he need for that?

题意概述

给定一张$n$个点$m$条边的无向图,其中$k$个点上有传送器,每条边都有一个权值。初始时所有传送器都处于关闭状态,你在$1$号点。你需要走到所有有传送器的点,将传送器打开。你可以从一个已经打开的传送器直接传送到另一个已经打开的传送器。求经过的所有边的权值和的最小值。
数据范围:$1 \le k \le n \le 10^5, \; 0 \le m \le 10^5$。

算法分析

我们假设所有的点都是传送器。根据最小生成树的性质,这时的最优解就是这张图的最小生成树。显然,如果我们把这张图抽象成只由$k$个有传送器的点构成的“传送图”,这时的最优解也就是“传送图”上的最小生成树。如何构造这张图呢?
计算出每个点到离它最近的传送器的位置$p_i$和距离$d_i$。对于一条权值为$w$的边$(u, v)$,我们将它想象一条权值为$(d_u+w+d_v)$的边$(p_u, p_v)$。这样,这张图上的所有边也就变成了连接$k$个传送器的边。这就可以用Kruskal求最小生成树来解决。这棵最小生成树的边权之和是固定的,因此当$1$号点没有传送器时,可以先走到离它最近的一个有传送器的点。
求$p_i$和$d_i$可以用多源SPFA来完成。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
long long n, m, k, nume, tot, ans, mi = 1e18;
long long h[100001], p[100001], d[100001], fa[100001], pre[100001];
bool in[100001];
struct edge { long long v, w, nxt; } e[200001];
struct line {
  long long u, v, w;
  bool operator < (const line &a) const {
    return d[u] + w + d[v] < d[a.u] + a.w + d[a.v];
  }
} l[200001];
void add_edge(long long u, long long v, long long w) {
  e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
  e[++nume].v = u, e[nume].w = w, e[nume].nxt = h[v], h[v] = nume;
}
void spfa() {
  queue<long long> que;
  while (!que.empty()) que.pop();
  for (int i = 1; i <= n; ++i)
    if (!d[i]) in[i] = true, que.push(i);
  while (!que.empty()) {
    int u = que.front(); in[u] = false, que.pop();
    for (int i = h[u]; i; i = e[i].nxt)
      if (d[e[i].v] > d[u] + e[i].w) {
        d[e[i].v] = d[u] + e[i].w, pre[e[i].v] = pre[u];
        if (!in[e[i].v]) in[e[i].v] = true, que.push(e[i].v);
      }
  }
}
long long get_fa(long long t) {
  return t == fa[t] ? t : fa[t] = get_fa(fa[t]);
}
int main()
{
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    long long u, v, w; cin >> u >> v >> w; add_edge(u, v, w);
  }
  memset(d, 0x1f, sizeof d), d[1] = 0, spfa(); cin >> k;
  for (int i = 1; i <= k; ++i) {
    cin >> p[i]; if (d[p[i]] < mi) mi = d[p[i]];
  }
  ans = mi, memset(d, 0x1f, sizeof d);
  for (int i = 1; i <= n; ++i) fa[i] = i, pre[i] = i;
  for (int i = 1; i <= k; ++i) d[p[i]] = 0; spfa();
  for (int i = 1; i <= n; ++i)
    for (int j = h[i]; j; j = e[j].nxt)
      l[++tot].u = i, l[tot].v = e[j].v, l[tot].w = e[j].w;
  sort(l + 1, l + tot + 1);
  for (int i = 1; i <= tot; ++i) {
    long long u = get_fa(pre[l[i].u]), v = get_fa(pre[l[i].v]);
    if (u != v) fa[u] = v, ans += d[l[i].u] + l[i].w + d[l[i].v];
  }
  cout << ans << endl;
  return 0;
}