## 题目描述

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.

## 算法分析

$${\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}

## 代码

/*
* 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;
for (int i = 2; i <= n; ++i)
dist[i] = mp[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;
}


## 题目描述

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.

## 算法分析

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, mp, ori, mx;
std :: pair <int, int> rec;
struct Line {
int u, v, d;
bool operator < (const Line &l) const {
return d < l.d;
}
} l;
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[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[i] && ! ~ mp[i] && ~ mx[i] && ori[i] - mx[i] < mn) mn = ori[i] - mx[i], p = i;
if (mn >= 0) break;
mp[p] = mp[p] = ori[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;
}


## 题目描述

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.

## 代码

#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;
struct edge {
long long v, c, id, nxt;
} e;
long long n, m, nume, h, fa, ans;
long long depth, up, ma, uid;
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] = t;
ma[e[i].v] = 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], ma[v]));
}
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];
}
u = get_fa(u), v = get_fa(v);
while (depth[u] > depth[p])
ans[uid[u]] = val - 1, q = get_fa(up[u]), fa[u] = q, u = get_fa(u);
while (depth[v] > depth[p])
ans[uid[v]] = val - 1, q = get_fa(up[v]), 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, 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;
}


## 题目描述

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?

## 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
long long n, m, k, nume, tot, ans, mi = 1e18;
long long h, p, d, fa, pre;
bool in;
struct edge { long long v, w, nxt; } e;
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;
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 = 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;
}