Recover Path

题目描述

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.

题意概述

给定一张$n$个点$m$条边的无向图,第$i$条边的权值为$t_i$。给定其中$k$个点,要求找一对点$s, t$,使得这$k$个点都在从$s$到$t$的某条最短路径上,并输出这条路径。保证有解。
数据范围:$1 \le n, m \le 10^5, \; 1 \le t_i \le 10000$。

算法分析

显然,存在一种方案使得$s, t$在给定的$k$个点中。
从$k$个点中任选一个点,找到在$k$个点中距离它最远的点$u$,这个点一定是$s$或$t$,可以用反证法证明。接着从$u$开始跑最短路,得到一张拓扑图。令$f_i$表示从$i$到$u$的最短路径上最多包含多少个$k$个点中的点。只要按距离从小到大枚举$i$,再枚举它的连边是否可以作为最短路径中的边。同时还要记录方案。

代码

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

Recruiting

题目描述

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.

题意概述

给定一张$n$个点$m$条边的无向图。两个人轮流选点。每个人的第一个点可以任意选,接下来每次都必须从与自己已选的点相邻的点中选一个。不能选已被选的点。若某一轮中某人不存在满足条件的点,则他这一轮不选。已知$1$、$2$、$3$号点是重要点,两人都想尽可能多地选到重要点。问在最优策略下,谁能选到更多的重要点。保证不会平局。
数据范围:$3 \le n \le 10^5, \; 2 \le m \le 2 \times 10^5$。

算法分析

易知不用考虑不能选已被选的点这个条件,因为这样一定不优。
令$d_{i, j}$表示$i$号点和$j$号点之间最短路径的长度。那么先手必胜当且仅当
$$\exists i, \; \forall j, \; \sum_{k=1}^3 [d_{k, i} \gt d_{k, j}] \lt 2$$
考虑它的意义。对于$i$号点,若存在一个$j$号点使得$i$号点到某两个重要点的距离严格大于$j$号点到这两个点的距离,则先手不能选$i$号点;否则,先手选$i$号点必胜。证明略。
所以只要枚举$i, j$就能判断。事实证明,稍加剪枝后的枚举可以通过此题。

代码

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

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

Hide

题意概述

有一棵$N$个节点的树,每个节点都是黑色或白色。有$Q$次操作,动态修改点的颜色,询问最远黑点对之间的距离。
数据范围:$1 \le N \le 10^5, \; 1 \le Q \le 5 \times 10^5$。

算法分析

考虑点分治,构造一棵重心树。为了方便,下面所有距离均表示在原树上的距离,堆均为大根堆。
设节点$i$在重心树上的父亲为$p_i$。对于每个节点$u$维护两个堆,第一个堆用来维护重心树上$u$子树中的所有黑点到$p_u$的距离,第二个堆用来维护重心树上$u$各个子树中距离$u$最远的黑点到$u$的距离。那么第二个堆可以借助第一个堆来维护。
接着需要一个全局的堆,用来维护所有节点第二个堆的前两个元素之和(经过该点的路径)以及所有黑点第二个堆的第一个元素(以该点为端点的路径)。
修改时,沿着重心树往上依次处理经过的节点,先在全局的堆中删除,再在第二个堆中删除,在第一个堆中修改后,维护第二个堆和全局的堆。

代码

/*
 * 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)
    read(u), read(v), tree::add_edge(u, v);
  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;
      read(p), tree::modify(p);
    }
  }
  return 0;
}

Count on a Tree II

题目描述

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$.

题意概述

给定一棵$N$个节点的树,每个节点都有权值。有$M$次询问,每次询问给出$u, v$,求从$u$到$v$的路径上有多少种不同的权值。
数据范围:$1 \le N \le 40000, \; 1 \le M \le 10^5$。

算法分析

统计权值种类数,容易想到莫队,但这是在一棵树上,所以需要稍微做些转化。
求出树的括号序(DFS,访问和离开节点时均记录),那么每个询问都可以转化为对括号序上某个区间的询问。但是,如果区间内的某个节点出现了两次,那么这个节点不应该对答案产生贡献。因此,算法执行时可以用两个数组维护,一个表示节点的出现次数,另一个表示权值的出现次数。
具体来讲,令$s_i, e_i$分别表示访问、离开节点$i$的时间。假设$s_u \le s_v$。若$u$是$v$祖先,那么就相当于询问区间$[s_u, s_v]$;否则,相当于询问区间$[e_u, s_v]$,但此时$u, v$的LCA并没有被计算到答案中,因此需要把它加上。

代码

/*
 * 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() {
  int n, m; read(n), read(m);
  for (int i = 1; i <= n; ++ i) {
    read(w[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) {
    read(u), read(v), q[i].id = 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;
}

Command Network

题目描述

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.

题意概述

给定平面上的$N$个点,其中$M$对点$(u_i, v_i)$之间可以连一条从$u_i$到$v_i$的有向边。要求使得从$1$号点出发可以到达其他所有点,求边的长度之和的最小值。
数据范围:$1 \le N \le 100, \; M \le 1 \le 10000$。

算法分析

最小树形图模板题。主要思想是先给对于每个点选一条最近的邻边,若没有形成环则退出,否则将环缩成一个点,重复以上步骤。

代码

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

Repairing Company

题目描述

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.

题意概述

有$Q$个街道和$M$个任务。给出两两街道之间的距离以及每个任务的地点$p_i$、开始时间$t_i$和花费时间$d_i$。问至少需要多少个工人才能完成所有任务。工人开始时可以在任意街道,一个工人只能同时做一个任务。
数据范围:$1 \le Q \le 20, \; 1 \le M \le 200$。

算法分析

首先用Floyd求出任意两点之间的距离,用$dist_{i, j}$表示。对于两个任务$i, j$,若$t_i+d_i+dist_{p_i, p_j} \le t_j$,那么做第$i$个任务的工人可以继续做第$j$个任务。显然,任务之间构成了一张有向无环图,问题转化为最小覆盖问题。将图中每个点$u$拆成$u_0, u_1$两个点。若原图中有一条边$(u, v)$,则在新图中连边$(u_0, v_1)$。答案就是$M$减去新图的最大匹配数。

代码

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

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

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

Long Live the Queen

题目描述

The Queen of Byteland is very loved by her people. In order to show her their love, the Bytelanders have decided to conquer a new country which will be named according to the queen’s name. This new country contains $N$ towns. The towns are connected by bidirectional roads and there is exactly ONE path between any two towns, walking on the country’s roads. For each town, the profit it brings to the owner is known. Although the Bytelanders love their queen very much, they don’t want to conquer all the $N$ towns for her. They will be satisfied with a non-empty subset of these towns, with the following $2$ properties: there exists a path from every town in the subset to every other town in the subset walking only through towns in the subset and the profit of the subset is maximum. The profit of a subset of the $N$ towns is equal to the sum of the profits of the towns which belong to the subset. Your task is to find the maximum profit the Bytelanders may get.

题意概述

给定一棵$N$个节点的树,每个节点都有权值。求它连通子图节点权值之和的最大值。
数据范围:$1 \le N \le 16000$。

算法分析

考虑树形DP。假定$1$号点为根节点。令$f_{0, i}$表示$i$的子树中以$i$为根的连通子图节点权值之和的最大值,$f_{1, i}$表示$i$的子树中不以$i$为根的连通子图节点权值之和的最大值。

代码

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

using namespace std;

namespace std {
  template <typename T> void maxify(T &a, T b) { b > a && (a = b); }
  template <typename T> void minify(T &a, T b) { b < a && (a = b); }
}

struct IOManager {
  template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
  inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
  inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
  template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
  template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
  inline void write(char c) { putchar(c); }
  inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
  template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
  static const int N = 16010;
  int n, nume, h[N], w[N], f[2][N];
  struct Edge {
    int v, nxt;
  } e[N << 1];
  void add_edge(int u, int v) {
    e[++ nume] = (Edge) { v, h[u] }, h[u] = nume;
    e[++ nume] = (Edge) { u, h[v] }, h[v] = nume;
  }
  void input() {
    io > n;
    for (int i = 1; i <= n; ++ i) io > w[i];
    for (int i = 1; i < n; ++ i) {
      int u, v; io > u > v, add_edge(u, v);
    }
  }
  void init() { memset(f, -0x3f, sizeof f); }
  void dfs(int t, int fa) {
    f[0][t] = w[t];
    for (int i = h[t]; i; i = e[i].nxt)
      if (e[i].v != fa) {
        dfs(e[i].v, t);
        maxify(f[1][t], max(f[0][e[i].v], f[1][e[i].v]));
        f[0][t] += max(f[0][e[i].v], 0);
      }
  }
  void process() { dfs(1, 0), io < max(f[0][1], f[1][1]) < '\n'; }

public:
  void solve() { input(), init(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}