## 题目描述

You have a convex polygon. The vertices of the polygon are successively numbered from $1$ to $n$. You also have a triangulation of this polygon, given as a list of $n-3$ diagonals.

There will be $2n-3$ undirected edges in the graph: $n-3$ edges in the triangulation and $n$ edges on the side of the polygon.

You can choose to conquer some vertices, and if you choose to conquer a vertex, you will conquer all the edges linked to this vertex.

Write a program to determine the minimum number of vertices you need to choose such that you can conquer all the edges. Note that you are not required to conquer all the vertices.

## 算法分析

• 如果这个点已被选择，那么与它相邻的两条边都已被覆盖；
• 否则，为了覆盖与它相邻的边，最优方案是选择与它相邻的两个点。

## 代码

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

int const N = 100005;
int nume, h[N], in[N], used[N], que[N];
struct Edge {
int v, nxt;
} e[N << 2];

void add_edge(int u, int v) {
e[++nume] = (Edge) {v, h[u]};
h[u] = nume;
}

int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= 2 * n - 3; ++i) {
int u, v;
scanf("%d%d", &u, &v);
++in[u];
++in[v];
}
int qb = 0, qe = 0;
for (int i = 1; i <= n; ++i) {
if (in[i] == 2) {
que[qe++] = i;
}
}
for (; qb < qe;) {
int cur = que[qb++];
if (!used[cur]) {
for (int i = h[cur]; i; i = e[i].nxt) {
if (in[e[i].v] > 2) {
used[e[i].v] = 1;
}
}
}
for (int i = h[cur]; i; i = e[i].nxt) {
--in[cur];
--in[e[i].v];
if (in[e[i].v] == 2) {
que[qe++] = e[i].v;
}
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
ans += used[i];
}
printf("%d\n", ans);
return 0;
}

## 题目描述

Traveller Gregory is famous for his ability to always choose the shortest path for his journey. Ostap is a journalist who seeks for information about the recent Gregory’s trip. He managed to get the evidence that during this trip Gregory visited a number of cities. However, there is no information about the order in which they were visited, and no information about the starting city and the ending city of Gregory’s trip (the entire trip is (one of) the shortest path between these cities). Help Ostap to find any shortest path that contains all specified cities.
Country in which Gregory traveled consists of $n$ cities and $m$ undirected roads between them. For each road Ostap knows the time it takes to travel it, and the “shortest” word above is with respect to those times.
It is guaranteed that there exists some shortest path going through all specified cities.

## 代码

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

static int const N = 100005;
int ne = 1, top, h[N], d[N], que[N], id[N], lst[N], pre[N], ans[N];
bool in[N], v[N];
struct Edge {
int u, v, w, nxt;
} e[N << 1];

void add_edge(int u, int v, int w) {
e[++ne] = (Edge){u, v, w, h[u]}, h[u] = ne;
e[++ne] = (Edge){v, u, w, h[v]}, h[v] = ne;
}

void spfa(int s) {
int qb = 0, qe = 1;
memset(d, 0x3f, sizeof d), d[s] = 0, que[0] = s, in[s] = 1;
for (; qb != qe;) {
int u = que[qb++];
in[u] = 0, qb == N && (qb = 0);
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;
if (!in[e[i].v]) {
if (qb == qe || d[e[i].v] > d[que[qb]])
que[qe++] = e[i].v, in[e[i].v] = 1, qe == N && (qe = 0);
else
!~--qb && (qb = N - 1), que[qb] = e[i].v, in[e[i].v] = 1;
}
}
}
}

int main() {
int n, m, k, t;
scanf("%d%d", &n, &m);
for (int i = 1, u, v, w; i <= m; ++i)
scanf("%d%d%d", &u, &v, &w), add_edge(u, v, w);
scanf("%d%d", &k, &t), v[t] = 1, spfa(t);
int s = t;
for (int i = 2; i <= k; ++i)
scanf("%d", &t), v[t] = 1, d[s] < d[t] && (s = t);
spfa(s);
for (int i = 1; i <= n; ++i)
id[i] = i;
std::sort(id + 1, id + n + 1, [&](int const &i, int const &j) { return d[i] < d[j]; });
for (int i : id) {
lst[i] += v[i];
for (int j = h[i]; j; j = e[j].nxt)
if (d[e[j].v] == d[i] + e[j].w && lst[e[j].v] < lst[i])
lst[e[j].v] = lst[i], pre[e[j].v] = j;
}
for (int i = 1; i <= n; ++i)
if (lst[i] == k) {
for (int j = pre[i]; j; j = pre[e[j].u])
ans[top++] = j >> 1;
break;
}
printf("%d\n", top);
for (int i = 0; i < top; ++i)
printf("%d ", ans[i]);
puts("");
return 0;
}


## 题目描述

Hurry! Two well-known software companies are recruiting programmers. Initially the total number of unemployed programmers is $n$. The companies are hiring them one by one, alternately. In one turn a company hires one of the programmers who has not been hired yet. The first company starts hiring.
Furthermore, there are some pairs of friends among the programmers. Of course, a programmer may have several friends. Friendship is a symmetrical relationship, so if $a$ is a friend of $b$ then $b$ is a friend of $a$.
All such pairs are known to the companies, and the companies follow the rule: a new programmer hired by a company must have at least one friend among the programmers already working in this company. The only exception is a programmer that a company starts with, he can be chosen arbitrarily. It may happen that after a number of turns a company can not longer hire anyone else according to the rule. In this case it stops hiring, while the other company can continue.
As usual, not all the programmers are created equal. There are three geniuses among them, and each company wants to hire as many geniuses as possible. Note that each company always can guarantee one genius to itself starting with a genius. So the question is, which company will hire two geniuses, if they both use optimal strategies.
Note that both companies have the full information during the hiring: friendship relations, who are geniuses and which programmers were hired by each company in each turn.

## 算法分析

$$\exists i, \; \forall j, \; \sum_{k=1}^3 [d_{k, i} \gt d_{k, j}] \lt 2$$

## 代码

#include <cstdio>
#include <cstring>

static int const N = 100005;
int ne, h[N], d[3][N], que[N];
struct Edge {
int v, nxt;
} e[N << 2];

void add_edge(int u, int v) {
e[++ne] = (Edge){v, h[u]}, h[u] = ne;
e[++ne] = (Edge){u, h[v]}, h[v] = ne;
}

void get_d(int s, int *d) {
int qb = 0, qe = 1;
d[s] = 0, que[0] = s;
for (; qb < qe;) {
int u = que[qb++];
for (int i = h[u]; i; i = e[i].nxt)
if (d[e[i].v] > d[u] + 1)
d[e[i].v] = d[u] + 1, que[qe++] = e[i].v;
}
}

int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0, u, v; i < m; ++i)
scanf("%d%d", &u, &v), add_edge(--u, --v);
memset(d, 0x3f, sizeof d);
for (int i = 0; i < 3; ++i)
get_d(i, d[i]);
bool flag = 0;
for (int i = 0; !flag && i < n; ++i) {
bool ls = 1;
for (int j = 0; ls && j < n; ++j) {
int cnt = 0;
for (int k = 0; k < 3; ++k)
cnt += d[k][i] > d[k][j];
ls &= cnt < 2;
}
flag |= ls;
}
puts(flag ? "1" : "2");
return 0;
}


## 题目描述

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


## 代码

/*
* Computer programmers do it byte by byte.
*/

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

template <typename T> void read(T &n) {
char c;
for (; (c = getchar()) < '0' || c > '9';)
;
for (n = c - '0'; (c = getchar()) >= '0' && c <= '9'; (n *= 10) += c - '0')
;
}

typedef int const ic;

static ic N = 100005;

class heap {
private:
std::priority_queue<int> que, buf;

void clear() {
for (; !que.empty() && !buf.empty() && que.top() == buf.top();
que.pop(), buf.pop())
;
}

public:
void push(ic &n) {
if (n)
que.push(n);
}

void erase(ic &n) {
if (n)
buf.push(n);
}

void pop() {
clear();
if (!que.empty())
que.pop();
}

int top() {
clear();
return que.empty() ? 0 : que.top();
}

int top2() {
clear();
if (que.empty())
return 0;
int tmp = que.top(), ret = tmp;
que.pop(), clear();
if (que.empty()) {
que.push(tmp);
return 0;
}
ret += que.top(), que.push(tmp);
return ret;
}
} global;

namespace tree {
int n, nume, h[N], col[N];
int tim, fi[N], dep[N], lca[N << 1][20];
int power[N << 1];
int root, up[N], size[N], mx[N], vis[N];
heap toup[N], me[N];
struct Edge {
int v, nxt;
} e[N << 1];

void add_edge(ic &u, ic &v) {
e[++nume] = (Edge){v, h[u]}, h[u] = nume;
e[++nume] = (Edge){u, h[v]}, h[v] = nume;
}

void dfs(ic &t, ic &fa) {
lca[++tim][0] = t, fi[t] = tim, dep[t] = dep[fa] + 1;
for (int i = h[t]; i; i = e[i].nxt)
if (e[i].v != fa)
dfs(e[i].v, t), lca[++tim][0] = t;
}

void init() {
for (int i = 2; i <= tim; i <<= 1)
++power[i];
for (int i = 1; i <= tim; ++i)
power[i] += power[i - 1];
for (int i = 1; i < 20; ++i)
for (int j = 1; j <= tim; ++j) {
ic k = std::min(tim, j + (1 << i - 1));
lca[j][i] = dep[lca[j][i - 1]] < dep[lca[k][i - 1]] ? lca[j][i - 1]
: lca[k][i - 1];
}
}

int get_lca(ic &u, ic &v) {
ic l = std::min(fi[u], fi[v]), r = std::max(fi[u], fi[v]);
ic len = power[r - l + 1], k = r - (1 << len) + 1;
return dep[lca[l][len]] < dep[lca[k][len]] ? lca[l][len] : lca[k][len];
}

int get_dist(ic &u, ic &v) {
ic lca = get_lca(u, v);
return dep[u] + dep[v] - 2 * dep[lca];
}

int get_size(ic &t, ic &fa) {
int ret = 1;
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v] && e[i].v != fa)
ret += get_size(e[i].v, t);
return ret;
}

void get_root(ic &t, ic &fa, ic &tot) {
size[t] = 1, mx[t] = 0;
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v] && e[i].v != fa)
get_root(e[i].v, t, tot), size[t] += size[e[i].v],
mx[t] = std::max(mx[t], size[e[i].v]);
(mx[t] = std::max(mx[t], tot - size[t])) < mx[root] && (root = t);
}

void init_heap(ic &t, ic &fa, ic &dep, heap &hp) {
hp.push(dep);
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v] && e[i].v != fa)
init_heap(e[i].v, t, dep + 1, hp);
}

void build(int t) {
vis[t] = true;
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v])
root = 0,
get_root(e[i].v, 0,
size[e[i].v] < size[t] ? size[e[i].v] : get_size(e[i].v, t)),
up[root] = t, init_heap(e[i].v, t, 1, toup[root]),
me[t].push(toup[root].top()), build(root);
global.push(me[t].top()), global.push(me[t].top2());
}

void modify(int t) {
ic p = t;
if (col[t])
global.erase(me[t].top());
else
global.push(me[t].top());
for (; up[t]; t = up[t]) {
if (col[up[t]])
global.erase(me[up[t]].top());
global.erase(me[up[t]].top2());
me[up[t]].erase(toup[t].top());
if (col[p])
toup[t].erase(get_dist(p, up[t]));
else
toup[t].push(get_dist(p, up[t]));
me[up[t]].push(toup[t].top());
if (col[up[t]])
global.push(me[up[t]].top());
global.push(me[up[t]].top2());
}
col[p] = !col[p];
}
} // namespace tree

int main() {
read(tree::n), tree::mx[0] = tree::n;
for (int i = 1, u, v; i < tree::n; ++i)
tree::dfs(1, 0), tree::init(), tree::get_root(1, 0, tree::n),
tree::build(tree::root);
for (int i = 1; i <= tree::n; ++i)
tree::col[i] = 1;
int q;
for (read(q); q--;) {
char c;
scanf(" %c", &c);
if (c == 'G')
printf("%d\n", global.top());
else {
int p;
}
}
return 0;
}


## 题目描述

You are given a tree with $N$ nodes. The tree nodes are numbered from $1$ to $N$. Each node has an integer weight.
We will ask you to perform the following operation:

• $u$ $v$: ask for how many different integers that represent the weight of nodes there are on the path from $u$ to $v$.

## 代码

/*
* Trap full -- please empty.
*/

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <typename T>
void read(T &n) {
char c; for (; (c = getchar()) < '0' || c > '9'; ) ;
for (n = c - '0'; (c = getchar()) >= '0' && c <= '9'; (n *= 10) += c - '0') ;
}

typedef int const ic;
typedef long long ll;

static ic N = 40005;
static ic M = 100005;
static ic K = 300;
std::map <int, int> num;
int nume, h[N], w[N], base[N], seq[N << 1];
int tim, st[N], ed[N], dep[N], up[N][16];
int mans, ml, mr, mvis[N], mrec[N], ans[M];
struct Edge {
int v, nxt;
} e[N << 1];
struct Query {
int l, r, lca, id;
bool operator < (const Query &q) const {
return l / K == q.l / K ? r < q.r : l / K < q.l / K;
}
} q[M];

void add_edge(ic &u, ic &v) {
e[++ nume] = (Edge) { v, h[u] }, h[u] = nume;
e[++ nume] = (Edge) { u, h[v] }, h[v] = nume;
}

void dfs(ic &t, ic &fa) {
seq[st[t] = ++ tim] = t, dep[t] = dep[fa] + 1, up[t][0] = fa;
for (int i = h[t]; i; i = e[i].nxt)
if (e[i].v != fa) dfs(e[i].v, t);
seq[ed[t] = ++ tim] = t;
}

int get_lca(int u, int v) {
if (dep[u] > dep[v]) std::swap(u, v);
for (int i = 15; ~ i; -- i)
if (dep[up[v][i]] >= dep[u]) v = up[v][i];
if (u == v) return u;
for (int i = 15; ~ i; -- i)
if (up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
return up[u][0];
}

void add(ic &u) {
if (mvis[u]) {
-- mrec[w[u]], mvis[u] = 0;
if (! mrec[w[u]]) -- mans;
} else {
if (! mrec[w[u]]) ++ mans;
++ mrec[w[u]], mvis[u] = 1;
}
}

void get(ic &l, ic &r) {
for (; ml < l;) add(seq[ml ++]);
for (; ml > l;) add(seq[-- ml]);
for (; mr < r;) add(seq[++ mr]);
for (; mr > r;) add(seq[mr --]);
}

int main() {
for (int i = 1; i <= n; ++ i) {
if (! num.count(w[i])) num[w[i]] = num.size();
w[i] = num[w[i]];
}
for (int i = 1, u, v; i < n; ++ i) read(u), read(v), add_edge(u, v);
dfs(1, 0);
for (int i = 1; i < 16; ++ i)
for (int j = 1; j <= n; ++ j) up[j][i] = up[up[j][i - 1]][i - 1];
for (int i = 1, u, v; i <= m; ++ i) {
if (st[u] > st[v]) std::swap(u, v);
if (ed[u] > ed[v]) q[i].l = st[u] + 1, q[i].r = st[v], q[i].lca = u;
else q[i].l = ed[u], q[i].r = st[v], q[i].lca = get_lca(u, v);
}
std::sort(q + 1, q + m + 1);
mans = ml = mr = mvis[1] = mrec[w[1]] = 1;
for (int i = 1; i <= m; ++ i) get(q[i].l, q[i].r), add(q[i].lca), ans[q[i].id] = mans, add(q[i].lca);
for (int i = 1; i <= m; ++ i) printf("%d\n", ans[i]);
return 0;
}


## 题目描述

After a long lasting war on words, a war on arms finally breaks out between littleken’s and KnuthOcean’s kingdoms. A sudden and violent assault by KnuthOcean’s force has rendered a total failure of littleken’s command network. A provisional network must be built immediately. littleken orders snoopy to take charge of the project.

With the situation studied to every detail, snoopy believes that the most urgent point is to enable littenken’s commands to reach every disconnected node in the destroyed network and decides on a plan to build a unidirectional communication network. The nodes are distributed on a plane. If littleken’s commands are to be able to be delivered directly from a node $A$ to another node $B$, a wire will have to be built along the straight line segment connecting the two nodes. Since it’s in wartime, not between all pairs of nodes can wires be built. snoopy wants the plan to require the shortest total length of wires so that the construction can be done very soon.

## 代码

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

static const int N = 1000;

int n, m, pre[N], id[N], vis[N];
double in[N];

struct Point {
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
Point operator - (const Point &p) const {
return Point(x - p.x, y - p.y);
}
double operator ! () const {
return sqrt(x * x + y * y);
}
} p[N];

struct Line {
int u, v; double w;
} l[N * N];

double calc(int root, int v, int e) {
double ret = 0;
while (1) {
for (int i = 0; i < v; ++ i) in[i] = 1e10;
for (int i = 0; i < e; ++ i)
if (l[i].w < in[l[i].v] && l[i].u != l[i].v)
pre[l[i].v] = l[i].u, in[l[i].v] = l[i].w;
for (int i = 0; i < v; ++ i)
if (i != root && in[i] == 1e10) return -1;
int cnt = 0; in[root] = 0;
memset(id, -1, sizeof id), memset(vis, -1, sizeof vis);
for (int i = 0; i < v; ++ i) {
ret += in[i]; int p = i;
while (vis[p] != i && ! ~ id[p] && p != root) vis[p] = i, p = pre[p];
if (p != root && ! ~ id[p]) {
for (int q = pre[p]; q != p; q = pre[q]) id[q] = cnt;
id[p] = cnt ++;
}
}
if (! cnt) break;
for (int i = 0; i < v; ++ i) if (! ~ id[i]) id[i] = cnt ++;
for (int i = 0; i < e; ++ i) {
if (id[l[i].u] != id[l[i].v]) l[i].w -= in[l[i].v];
l[i].u = id[l[i].u], l[i].v = id[l[i].v];
}
v = cnt, root = id[root];
}
return ret;
}

int main() {
while (~ scanf("%d%d", &n, &m)) {
for (int i = 0; i < n; ++ i) scanf("%lf%lf", &p[i].x, &p[i].y);
for (int i = 0; i < m; ++ i) {
scanf("%d%d", &l[i].u, &l[i].v), -- l[i].u, -- l[i].v;
if (l[i].u != l[i].v) l[i].w = ! (p[l[i].u] - p[l[i].v]); else l[i].w = 1e10;
}
double ans = calc(0, n, m);
if (ans == -1) printf("poor snoopy\n");
else printf("%.2lf\n", ans);
}
return 0;
}

## 题目描述

Lily runs a repairing company that services the $Q$ blocks in the city. One day the company receives $M$ repair tasks, the $i$-th of which occurs in block $p_i$, has a deadline $t_i$ on any repairman’s arrival, which is also its starting time, and takes a single repairman $d_i$ time to finish. Repairmen work alone on all tasks and must finish one task before moving on to another. With a map of the city in hand, Lily want to know the minimum number of repairmen that have to be assign to this day’s tasks.

## 代码

#include <cstdio>
#include <cstring>

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

static const int Q = 25;
static const int M = 405;
int mp[Q][Q], p[M], t[M], d[M];
int nume, h[M];
struct Edge {
int v, f, nxt;
} e[M * M << 1];

void add_edge(int u, int v, int f) {
e[++ nume] = (Edge) { v, f, h[u] }, h[u] = nume;
e[++ nume] = (Edge) { u, 0, h[v] }, h[v] = nume;
}

namespace flow {
int S, T, g[M], dist[M], que[M], gap[M];

bool bfs() {
memcpy(g, h, sizeof h);
memset(dist, 0x3f, sizeof dist), memset(gap, 0, sizeof gap);
int qb = 0, qe = 1; dist[T] = 0, que[0] = T, ++ gap[0];
while (qb < qe) {
int u = que[qb ++];
for (int i = g[u]; i; i = e[i].nxt)
if (e[i ^ 1].f && dist[e[i].v] > dist[u] + 1)
dist[e[i].v] = dist[u] + 1, que[qe ++] = e[i].v, ++ gap[dist[e[i].v]];
}
return dist[S] < 1e9;
}

int dfs(int t, int low) {
if (t == T) return low;
int used = 0;
for (int &i = g[t]; i; i = e[i].nxt)
if (e[i].f && dist[e[i].v] == dist[t] - 1) {
int flow = dfs(e[i].v, min(e[i].f, low - used));
if (flow) e[i].f -= flow, e[i ^ 1].f += flow, used += flow;
if (used == low || dist[S] > T) return used;
}
if (! -- gap[dist[t]]) dist[S] = T + 1;
else ++ gap[++ dist[t]], g[t] = h[t];
return used;
}

int maxflow() {
bfs(); int flow = 0;
while (dist[S] <= T) flow += dfs(S, 1e9);
return flow;
}
}

int main() {
int q, m;
while (scanf("%d%d", &q, &m), q) {
nume = 1, memset(h, 0, sizeof h);
flow :: S = m << 1, flow :: T = (m << 1) + 1;
for (int i = 0; i < q; ++ i)
for (int j = 0; j < q; ++ j) scanf("%d", &mp[i][j]);
for (int i = 0; i < q; ++ i)
for (int j = 0; j < q; ++ j) if (! ~ mp[i][j]) mp[i][j] = 1e9;
for (int k = 0; k < q; ++ k)
for (int i = 0; i < q; ++ i)
for (int j = 0; j < q; ++ j) mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
for (int i = 0; i < m; ++ i) scanf("%d%d%d", &p[i], &t[i], &d[i]), -- p[i];
for (int i = 0; i < m; ++ i)
for (int j = 0; j < m; ++ j) if (i != j && t[i] + d[i] + mp[p[i]][p[j]] <= t[j]) add_edge(i, j + m, 1);
for (int i = 0; i < m; ++ i) add_edge(flow :: S, i, 1), add_edge(i + m, flow :: T, 1);
printf("%d\n", m - flow :: maxflow());
}
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[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;
}


## 题目描述

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.

## 代码

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