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

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

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

Traffic Lights

题目描述

In the city of Dingilville the traffic is arranged in an unusual way. There are junctions and roads connecting the junctions. There is at most one road between any two different junctions. There is no road connecting a junction to itself. Travel time for a road is the same for both directions. At every junction there is a single traffic light that is either blue or purple at any moment. The color of each light alternates periodically: blue for certain duration and then purple for another duration. Traffic is permitted to travel down the road between any two junctions, if and only if the lights at both junctions are the same color at the moment of departing from one junction for the other. If a vehicle arrives at a junction just at the moment the lights switch it must consider the new colors of lights. Vehicles are allowed to wait at the junctions. You are given the city map which shows:

  • the travel times for all roads (integers);
  • the durations of the two colors at each junction (integers);
  • and the initial color of the light and the remaining time (integer) for this color to change at each junction.

Your task is to find a path which takes the minimum time from a given source junction to a given destination junction for a vehicle when the traffic starts. In case more than one such path exists you are required to report only one of them.

题意概述

给定一张$N$个点$M$条边的图,每个点要么是蓝色要么是紫色,且会随着时间变化。可以从点$u$走到点$v$的条件是两点间有一条边且从$u$出发时$u, v$两点颜色相同。给定每个点的初始颜色以及两种颜色交替的时间,给定走过每条边所需的时间,求从$s$到$t$至少需要多少时间(可以在某个点停留)。
数据范围:$2 \le N \le 300, \; 1 \le M \le 14000$。

算法分析

显然这是一道最短路题,但在计算距离时有点不同。若走到点$u$的最短时间为$t$,打算更新点$v$,则需要计算出$t$之后最早的时刻$t’$满足$u, v$两点颜色相同,并用$t’+w_{u, v}$更新$v$。
寻找时刻$t’$可以直接暴力。有个显而易见的结论:如果在$t$之后,$u, v$同时改变颜色的次数超过连续$3$次,则$t’$不存在。

代码

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

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; 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; 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) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    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 Junction { bool c; int r, t[2]; };

struct Edge { int v, l, nxt; };

struct Solver {
private:
  static const int N = 310;
  static const int M = 14010;
  int s, t, n, m, nume, h[N], dist[N], pre[N];
  bool in[N];
  Junction junc[N];
  Edge e[M << 1];
  void add_edge(int u, int v, int l) {
    e[++ nume] = (Edge) { v, l, h[u] }, h[u] = nume;
    e[++ nume] = (Edge) { u, l, h[v] }, h[v] = nume;
  }
  void input() {
    io > s > t > n > m;
    for (int i = 1; i <= n; ++ i) {
      char c; io > c > junc[i].r > junc[i].t[0] > junc[i].t[1], junc[i].c = c == 'P';
    }
    for (int i = 1; i <= m; ++ i) {
      int u, v, l; io > u > v > l, add_edge(u, v, l);
    }
  }
  int get(int u, int v, int t) {
    int cu = junc[u].c, tuu = 0, cv = junc[v].c, tvv = 0;
    if (t >= junc[u].r) {
      cu = ! cu; int cnt = (t - junc[u].r) / (junc[u].t[0] + junc[u].t[1]);
      tuu = junc[u].r + cnt * (junc[u].t[0] + junc[u].t[1]);
      if (tuu + junc[u].t[cu] <= t) tuu += junc[u].t[cu], cu = ! cu;
    }
    if (t >= junc[v].r) {
      cv = ! cv; int cnt = (t - junc[v].r) / (junc[v].t[0] + junc[v].t[1]);
      tvv = junc[v].r + cnt * (junc[v].t[0] + junc[v].t[1]);
      if (tvv + junc[v].t[cv] <= t) tvv += junc[v].t[cv], cv = ! cv;
    }
    if (cu == cv) return t;
    int cnt = 0;
    while (cu != cv) {
      if (cnt > 3) return 1e9;
      if (tuu + (tuu ? junc[u].t[cu] : junc[u].r) < tvv + (tvv ? junc[v].t[cv] : junc[v].r)) tuu += (tuu ? junc[u].t[cu] : junc[u].r), cu = ! cu;
      else if (tuu + (tuu ? junc[u].t[cu] : junc[u].r) > tvv + (tvv ? junc[v].t[cv] : junc[v].r)) tvv += (tvv ? junc[v].t[cv] : junc[v].r), cv = ! cv;
      else tuu += (tuu ? junc[u].t[cu] : junc[u].r), cu = ! cu, tvv += (tvv ? junc[v].t[cv] : junc[v].r), cv = ! cv, ++ cnt;
    }
    return max(tuu, tvv);
  }
  int spfa() {
    memset(dist, 0x7f, sizeof dist), dist[s] = 0;
    queue <int> que; que.push(s), in[s] = true;
    while (! que.empty()) {
      int u = que.front(); que.pop(), in[u] = false;
      for (int i = h[u]; i; i = e[i].nxt) {
        int t = get(u, e[i].v, dist[u]);
        if (dist[e[i].v] > t + e[i].l) {
          dist[e[i].v] = t + e[i].l, pre[e[i].v] = u;
          if (! in[e[i].v]) que.push(e[i].v), in[e[i].v] = true;
        }
      }
    }
    return dist[t];
  }
  void print(int t) {
    if (! t) return;
    print(pre[t]), io < t < ' ';
  }
  void process() {
    int dis = spfa();
    io < (dis < 1e9 ? dis : 0) < '\n';
    if (dis < 1e9) print(t), io < '\n';
  }

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

int main() {
  solver.solve();
  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;
}

Legacy

题目描述

Rick and his co-workers have made a new radioactive formula and a lot of bad guys are after them. So Rick wants to give his legacy to Morty before bad guys catch them.
There are n planets in their universe numbered from $1$ to $n$. Rick is in planet number $s$ (the earth) and he doesn’t know where Morty is. As we all know, Rick owns a portal gun. With this gun he can open one-way portal from a planet he is in to any other planet (including that planet). But there are limits on this gun because he’s still using its free trial.
By default he can not open any portal by this gun. There are $q$ plans in the website that sells these guns. Every time you purchase a plan you can only use it once but you can purchase it again if you want to use it more.
Plans on the website have three types:

  1. With a plan of this type you can open a portal from planet $v$ to planet $u$.
  2. With a plan of this type you can open a portal from planet $v$ to any planet with index in range $[l, r]$.
  3. With a plan of this type you can open a portal from any planet with index in range $[l, r]$ to planet $v$.

Rick doesn’t known where Morty is, but Unity is going to inform him and he wants to be prepared for when he finds and start his journey immediately. So for each planet (including earth itself) he wants to know the minimum amount of money he needs to get from earth to that planet.

题意概述

有$n$个点以及$q$条边。边有$3$种类型:①从点$v$到点$u$;②从点$v$到编号在$[l, r]$之间的点;③从编号在$[l, r]$之间的点到点$v$。每条边都有一个权值$w$。求从点$s$出发到其他所有点的最短路径长度。
数据范围:$1 \le n, q \le 10^5, \; 1 \le w \le 10^9$。

算法分析

分别从上到下、从下到上建立线段树,但边的方向均为从上到下,边权均为$0$。
Two Segment Trees
如图,红色边表示线段树中的边。对于输入的每一条边,在这张图中建立相对应的边:①直接在最中间一层连边;②从最中间一层的点向上面的线段树连边;③从下面的线段树向最中间一层的点连边。最后跑一遍最短路即可。显然,点的数目为$O(n)$,边的数目为$O(n\log n)$,因此可以AC。

代码

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
struct node_type {
    long long l, r, child[2];
} node[2000001];
struct edge {
    long long v, w, nxt;
} e[2000001];
long long n, q, s, dist[2000001], tot, nume, h[2000001];
bool in[2000001];
queue<long long> que;
void add_edge(long long u, long long v, long long w) {
    if (u == v) return;
    e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
}
void build_tree(long long root, int mode) {
    long long mid = node[root].l + node[root].r >> 1;
    if (node[root].l == mid) node[root].child[0] = node[root].l;
    else {
        node[++tot].l = node[root].l, node[tot].r = mid;
        node[root].child[0] = tot, build_tree(tot, mode);
    }
    if (mid + 1 == node[root].r) node[root].child[1] = node[root].r;
    else {
        node[++tot].l = mid + 1, node[tot].r = node[root].r;
        node[root].child[1] = tot, build_tree(tot, mode);
    }
    if (mode) {
        add_edge(node[root].child[0], root, 0);
        add_edge(node[root].child[1], root, 0);
    } else {
        add_edge(root, node[root].child[0], 0);
        add_edge(root, node[root].child[1], 0);
    }
}
void insert_line(long long root, long long l, long long r, long long v, long long w, int mode) {
    if (l == node[root].l && r == node[root].r) {
        if (!mode) add_edge(v, root, w);
        else add_edge(root, v, w);
        return;
    }
    if (r < node[node[root].child[1]].l) insert_line(node[root].child[0], l, r, v, w, mode);
    else if (l > node[node[root].child[0]].r) insert_line(node[root].child[1], l, r, v, w, mode);
    else {
        insert_line(node[root].child[0], l, node[node[root].child[0]].r, v, w, mode);
        insert_line(node[root].child[1], node[node[root].child[1]].l, r, v, w, mode);
    }
}
void spfa() {
    memset(dist, 0x1f, sizeof(dist));
    while (!que.empty()) que.pop();
    que.push(s), in[s] = true, dist[s] = 0;
    while (!que.empty()) {
        long long t = que.front(); que.pop(); in[t] = false;
        for (long long i = h[t]; i; i = e[i].nxt) {
            if (dist[e[i].v] > dist[t] + e[i].w) {
                dist[e[i].v] = dist[t] + e[i].w;
                if (!in[e[i].v]) que.push(e[i].v), in[e[i].v] = true;
            }
        }
    }
}
int main()
{
    scanf("%lld%lld%lld", &n, &q, &s);
    for (int i = 1; i <= n; ++i) {
        node[i].l = node[i].r = i;
    }
    tot = n + 2;
    node[n + 1].l = node[n + 2].l = 1;
    node[n + 1].r = node[n + 2].r = n;
    if (n > 1) build_tree(n + 1, 0), build_tree(n + 2, 1);
    for (long long i = 1, t, v, u, l, r, w; i <= q; ++i) {
        scanf("%lld", &t);
        if (t == 1) {
            scanf("%lld%lld%lld", &v, &u, &w);
            add_edge(v, u, w);
        } else {
            scanf("%lld%lld%lld%lld", &v, &l, &r, &w);
            insert_line(n + t - 1, l, r, v, w, t - 2);
        }
    }
    spfa();
    for (int i = 1; i <= n; ++i) {
        if (dist[i] != dist[0]) printf("%lld ", dist[i]);
        else printf("-1 ");
    }
    printf("\n");
    return 0;
}

Complete the Graph

题目描述

ZS the Coder has drawn an undirected graph of $n$ vertices numbered from $0$ to $n-1$ and m edges between them. Each edge of the graph is weighted, each weight is a positive integer.
The next day, ZS the Coder realized that some of the weights were erased! So he wants to reassign positive integer weight to each of the edges which weights were erased, so that the length of the shortest path between vertices $s$ and $t$ in the resulting graph is exactly $L$. Can you help him?

题意概述

给定一张连通无向图,其中所有边的权值均为自然数。要求将所有权值为$0$的边的权值变成任意一个不大于$10^{18}$的正整数,使得从$s$到$t$的最短路径的长度为$L$。
数据范围:$2 \le n \le 1000, \; 1 \le m \le 10000, \; 1 \le L \le 10^9, \; 0 \le s, t \le n-1$。

算法分析

首先将权值为$0$的边的权值变成无穷大,求一次最短路,若$s$和$t$之间的距离$dist \lt L$则无解。
若$dist=L$,则已得到可行解。
若$dist \gt L$,枚举初始权值为$0$的边,将它的权值变成$1$,求一次最短路,若$dist \le L$则说明已有可行解,把这条边的权值增加$L-dist$,即得到可行解。若所有初始权值为$0$的边都已枚举且$dist \gt L$,则说明无解。

代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
long long n, m, L, s, t, dist[1001], line[1001][1001];
bool flag, in[1001], sign[1001][1001];
void spfa(int p = -1, int q = -1) {
    queue<int> que;
    while (!que.empty()) que.pop();
    memset(in, false, sizeof(in));
    if (p == -1) {
        memset(dist, 0x1f, sizeof(dist));
        que.push(s), dist[s] = 0, in[s] = true;
    } else {
        if (dist[p] > dist[q]) p ^= q ^= p ^= q;
        que.push(p), in[p] = true;
    }
    while (!que.empty()) {
        long long u = que.front();
        que.pop();
        in[u] = false;
        for (int i = 0; i < n; ++i) {
            if (line[u][i] && dist[i] > dist[u] + line[u][i]) {
                dist[i] = dist[u] + line[u][i];
                if (!in[i]) que.push(i), in[i] = true;
            }
        }
    }
}
int main()
{
    cin >> n >> m >> L >> s >> t;
    for (int i = 1; i <= m; ++i) {
        long long x, y, w;
        cin >> x >> y >> w;
        line[x][y] = line[y][x] = w;
        if (!w) sign[x][y] = sign[y][x] = true;
    }
    spfa();
    if (dist[t] < L) {
        cout << "NO" << endl;
        return 0;
    } else if (dist[t] > L) {
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (sign[i][j]) {
                    line[i][j] = line[j][i] = 1;
                    sign[i][j] = sign[j][i] = false;
                    spfa(i, j);
                    if (dist[t] <= L) {
                        line[i][j] = line[j][i] = L - dist[t] + 1;
                        flag = true; break;
                    }
                }
            }
            if (flag) break;
        }
    } else flag = true;
    if (!flag) cout << "NO" << endl;
    else {
        cout << "YES" << endl;
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (line[i][j] || sign[i][j]) {
                    cout << i << ' ' << j << ' ';
                    if (line[i][j]) cout << line[i][j];
                    if (sign[i][j]) cout << (long long) 1e18;
                    cout << endl;
                }
            }
        }
    }
    return 0;
}