Perishable Roads

题目描述

In the country of Never, there are $n$ cities and a well-developed road system. There is exactly one bidirectional road between every pair of cities, thus, there are as many as ${n(n - 1) \over 2}$ roads! No two roads intersect, and no road passes through intermediate cities. The art of building tunnels and bridges has been mastered by Neverians.

An independent committee has evaluated each road of Never with a positive integer called the perishability of the road. The lower the road’s perishability is, the more pleasant it is to drive through this road.

It’s the year of transport in Never. It has been decided to build a museum of transport in one of the cities, and to set a single signpost directing to some city (not necessarily the one with the museum) in each of the other cities. The signposts must satisfy the following important condition: if any Neverian living in a city without the museum starts travelling from that city following the directions of the signposts, then this person will eventually arrive in the city with the museum.

Neverians are incredibly positive-minded. If a Neverian travels by a route consisting of several roads, he considers the perishability of the route to be equal to the smallest perishability of all the roads in this route.

The government of Never has not yet decided where to build the museum, so they consider all $n$ possible options. The most important is the sum of perishabilities of the routes to the museum city from all the other cities of Never, if the travelers strictly follow the directions of the signposts. The government of Never cares about their citizens, so they want to set the signposts in a way which minimizes this sum. Help them determine the minimum possible sum for all n possible options of the city where the museum can be built.

题意概述

给定一张$n$个点的完全图，边权均为正数。定义一条路径的长度为这条路径上所有边权的最小值。现需要在其中某个城市建造博物馆，并在其他城市各放置一个指向标。也就是说，当你在博物馆以外的城市时，你只能沿着当前城市指向标所指向的边走。对于$k \in [1, n]$，求出在城市$k$建立博物馆时，其他各城市到博物馆的距离之和的最小值。

数据范围：$2 \le n \le 2000$。

算法分析

令$w_{i, j}$表示城市$i$和城市$j$之间的边权。

首先，假设有两个不同城市$a, b$的指向标指向了同一城市$c$，若$w_{a, c} \le w_{b, c}$，那么将$b$的指向标指向$a$并不会使答案变劣，反之亦然。因此，一定存在一种最优解的方案构成了一条链。

其次，令$p=\min(w_{i, j} \mid i \neq j)$，可以将所有边权减去$p$，对最优方案没有影响，只要在最后把答案加上$p(n-1)$。

考虑经我们修改过的图，如果一条路径经过了$0$边（边权为$0$的边），那么它对答案没有贡献。由于一定存在一条链的最优解，且图是完全图，因此只要考虑从每个点出发到与$0$边相邻的点的距离之和的最小值。

假设我们走过的路径中，第$i$个点和第$(i+1)$个点之间的边的权值为$a_i$。令$k$满足$a_{1..k-1} \gt 0 \land a_k=0$，那么$\forall i \le k-3, \ a_i \gt a_{i+1}$。否则，第$(i+1)$个点和第$(i+2)$个点之间的边产生的贡献为$a_i$，与第$(i+2)$个点是什么无关，那么我们可以直接将第$(i+1)$个点连到一个与$0$边相邻的点上，使$k$变小，答案更优。

这样一来，对于前$(k-3)$个点来说，它们产生的贡献就是$\sum_{i=1}^{k-3} a_i$，只要考虑$a_{k-1}$和$a_{k-2}$的关系。若$a_{k-1} \lt a_{k-2}$，那么贡献的计算方法与前面的点一样；否则，贡献为$2a_{k-2}$。

具体实现时，可以令$d_i$表示第$i$个点到与$0$边相邻的点的“距离”（非题目定义的距离）的最小值。可以将$d_i$初始化为$2\min(w_{i, j})$，因为从$i$走一步到$j$之后，下一步可以走到任意点，贡献最多为$w_{i, j}$。接下来只要用 Dijkstra 求最短路。

代码

#include <cstdio>
#include <cstring>

#define int long long

int min(int a, int b) {
  return a < b ? a : b;
}

void read(int &t) {
  char c; while((c = getchar()) < '0' || c > '9') ; t = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') (t *= 10) += c - '0';
}

static const int N = 2010;
int mp[N][N], dist[N];
bool vis[N];

signed main() {
  int n, mn = 1000000001; read(n);
  for (int i = 1; i < n; ++ i)
    for (int j = i + 1; j <= n; ++ j) read(mp[i][j]), mn = min(mn, mp[j][i] = mp[i][j]);
  for (int i = 1; i <= n; ++ i)
    for (int j = 1; j <= n; ++ j) if (i != j) mp[i][j] -= mn;
  for (int i = 1; i <= n; ++ i) {
    dist[i] = 1000000001;
    for (int j = 1; j <= n; ++ j) if (i != j) dist[i] = min(dist[i], mp[i][j]);
    dist[i] <<= 1;
  }
  for (int _ = n; _; -- _) {
    int mn = 1000000000000000ll, p = -1;
    for (int i = 1; i <= n; ++ i) if (! vis[i] && dist[i] < mn) mn = dist[p = i];
    vis[p] = true;
    for (int i = 1; i <= n; ++ i) dist[i] = min(dist[i], dist[p] + mp[i][p]);
  }
  for (int i = 1; i <= n; ++ i) printf("%lld/n", dist[i] + mn * (n - 1));
  return 0;
}