题目链接

LOJ2718

题目概括

给定一张 $N$ 个点,$M$ 条无向带权边的图。

边权为二元组 $(x,y)$,表示长度为 $x$,海拔为 $y$。

每次询问给定 $K,P$ 表示起点为 $K$,当前能够通过的边必须满足海拔 $\ge P$。

如果不能通过某一条边,会从当前节点走到 $1$ 号节点。

求到 $1$ 号节点需要走的最短路程。

数据范围:$N\leq 2\times 10^5, M\leq 4\times 10^5$

每一个询问独立,且询问强制在线

思路要点

问题的条件等价于找到一条路径,满足海拔最小的路径最大。

这显然就是LOJ137 最小瓶颈路

按照套路建立 $Kruskal$ 重构树。

以某一个节点为根节点的子树,一定是可以直接到达,所以只需要用倍增找到最后一个满足的祖先节点,其子树内的最小值就是答案。

时间复杂度 $\mathcal O(nlogn)$

代码

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

namespace FastIO {
  template <class T> 
  void rd(T& x) {
    x = 0;
    char ch = 0;
    bool f = 0;
    while (!isdigit(ch)) f |= ch == '-', ch = getchar(); 
    while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
    f ? x = -x : 1;
  }

  template <class T> 
  void ptf(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) ptf(x / 10);
    putchar(x % 10 + 48);
  }

  void read(int& x) { rd(x); }
  void read(long long& x) { rd(x); }
  void read(unsigned int& x) { rd(x); }
  void read(unsigned long long& x) { rd(x); }
  void read(char& x) { x = getchar(); }
  void read(string& x) { cin >> x; }
  template <class T, class R> 
  void read(pair<T, R>& x) {
    read(x.first), read(x.second);
  }
  template <class T> 
  void read(vector<T>& x) { 
    for (auto& ele : x) read(x); 
  }

  void write(int x) { ptf(x); }
  void write(long long x) { ptf(x); }
  void write(unsigned long long x) { ptf(x); }
  void write(unsigned int x) { ptf(x); }
  void write(char x) { putchar(x); }
  void write(char* x) { printf("%s", x); }
  void write(string x) { cout << x; }
  template <class T> 
  void write(vector<T> x) {
    for (auto ele : x)  (x); 
  }
  template <class T, class R> 
  void write(pair<T, R> x) {
    write(x.first), putchar(','), write(x.second);
  }
  template <class T> 
  void writeln(T x) {
    write(x), puts("");
  }
}

using FastIO::read;
using FastIO::write;
using FastIO::writeln;

namespace ShortPath {

const int N = 4e5 + 5; 

struct State {
  int u;
  ll dis;

  State() { }

  State(int a, ll b) {
    u = a, dis = b; 
  }

  bool operator<(const State& rhs) const { 
    return dis > rhs.dis;
  }
};

vector<pair<int, ll>> g[N];
int n;
ll dis[N];
bool vis[N];

void init(int x) {
  n = x; 
  for (int i = 1; i <= n; i++) { g[i].clear(); }
}

void add(int u, int v, int w) {
  g[u].push_back(make_pair(v, w));
}

void dijkstra(int s) {
  priority_queue<State> q;
  memset(dis, 0x3f, sizeof dis);
  memset(vis, 0, sizeof vis);
  dis[s] = 0;
  q.push(State(s, 0));
  while (!q.empty()) {
    int u = q.top().u; 
    q.pop();
    if (vis[u]) { continue; }
    vis[u] = 1; 
    for (auto it : g[u]) {
      if (dis[it.first] > dis[u] + it.second) {
        dis[it.first] = dis[u] + it.second;
        q.push(State(it.first, dis[it.first]));
      }
    }
  }
}

}

const int N = 2e5 + 5, M = 4e5 + 5, LOG = 23; 

struct Edg {
  int u, v, w; 
} edg[M];

int f[N << 1], fa[N << 1], g[N << 1];
ll val[N << 1];
int ft[LOG + 2][N << 1];
int n, m, tot;

int get(int x) {
  return fa[x] == x ? fa[x] : fa[x] = get(fa[x]);
}

void init() {
  ShortPath::init(n);
  tot = n; 
  memset(ft, 0, sizeof ft);
  memset(f, 0, sizeof f);
  memset(val, 0, sizeof val);
  for (int i = 1; i <= n * 2; i++) { fa[i] = i; }
}

int query(int u, int vl) {
  for (int i = LOG; i >= 0; i--) {
    if (ft[i][u] && g[ft[i][u]] > vl) { u = ft[i][u]; }
  }
  return val[u]; 
}

int main() {
  freopen("return.in", "r", stdin);
  freopen("return.out", "w", stdout);
  int t; 
  read(t);
  while (t--) {
    read(n), read(m);
    init();
    for (int i = 1; i <= m; i++) { 
      int len; 
      read(edg[i].u), read(edg[i].v), read(len), read(edg[i].w); 
      ShortPath::add(edg[i].u, edg[i].v, len);
      ShortPath::add(edg[i].v, edg[i].u, len);
    }
    ShortPath::dijkstra(1);
    sort(edg + 1, edg + 1 + m, [](Edg a, Edg b) { 
      return a.w > b.w;
    });
    for (int i = 1; i <= n; i++) { val[i] = ShortPath::dis[i]; }
    for (int i = 1; i <= m; i++) { 
      int p1 = get(edg[i].u), p2 = get(edg[i].v);
      if (p1 != p2) {
        ++tot; 
        g[tot] = edg[i].w;
        fa[p1] = fa[p2] = tot;
        val[tot] = min(val[p1], val[p2]);
        ft[0][p1] = ft[0][p2] = tot; 
      }
    }
    ft[0][tot] = ft[1][tot] = tot; 
    for (int i = 1; i <= LOG; i++) {
      for (int j = 1; j <= tot; j++) { ft[i][j] = ft[i - 1][ft[i - 1][j]]; }
    }
    ll lastAns = 0;
    int q, k, s; 
    read(q), read(k), read(s);
    while (q--) {
      int v, p; 
      read(v), read(p);
      v = (v + k * lastAns - 1) % n + 1; 
      p = (p + k * lastAns) % (s + 1); 
      writeln(lastAns = query(v, p));
    }
  }
  return 0;
}

后言

  • 对于图中路径最大值最小或者最小值最大,都是最小瓶颈路的模型,可以先按照 $Kruscal$ 重构树的方案来考虑问题,或者还可以用并查集离线处理。
最后修改:2020 年 03 月 31 日 09 : 06 AM
如果觉得我的文章对你有用,请随意赞赏