aji波兰题！（迫真）

啊波兰题真好康（一转）

考虑怎么去除非加油站的影响……对于每两个加油站，取他们的最短路，然后建出来一个图，这个图的MST上的路径的走法就事最优走法。

但这样显然会凉……因为\(s\)肥肠巨大，会T。然后我们考虑多源最短路，并且给每个点标记到它最近的加油站（称为来源）。那么考虑两条加油站间的路径，上面一定有一条边满足边两个端点不一样（证明考虑……如果所有边两边端点的来源都一样，那么所有边的来源会同时事那两个加油站）。

然后一个小问题事，如果一个点有多个来源，只考虑一个会出事吗？这个事不会的。比如说有三个加油站\(a\)、\(b\)、\(c\)，如果说三者到一个点的最短路都一样，那么我们考虑只取\(a\)。如果\(b\)和\(c\)本来能连一条边，但现在因为这个连不了了，那他们还是能同时各和\(a\)连一条长度和原来的那条边长度一样的边，所以事实上没有什么笋丝。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
const int maxn = 200005, maxm = 400005;
int first[maxn];
int next[maxm], to[maxm], dist[maxm];
bool dir[maxm];
void add_edge(int u, int v, int w, bool d = true) {
  static int cnt = 0;
  cnt ++; next[cnt] = first[u]; first[u] = cnt;
  to[cnt] = v; dist[cnt] = w; dir[cnt] = d;
}
void ins_edge(int u, int v, int w) {
  add_edge(u, v, w); add_edge(v, u, w, false);
}

using ll = long long;
using pii = std::pair<ll, int>;
int n; std::vector<int> V;
ll d[maxn]; int src[maxn];
bool vis[maxn];
void dij() {
  memset(d, 0x1f, sizeof(d));
  std::priority_queue<pii, std::vector<pii>, std::greater<pii> > Q;
  for(auto p : V) {
    d[p] = 0; src[p] = p;
    Q.push(std::make_pair(0LL, p));
  }
  while(!Q.empty()) {
    int u = Q.top().second; Q.pop();
    if(vis[u]) continue;
    vis[u] = true;
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(d[u] + (ll(dist[i])) < d[v]) {
        d[v] = d[u] + (ll(dist[i]));
        src[v] = src[u];
        Q.push(std::make_pair(d[v], v));
      }
    }
  }
}

int p[maxn], rk[maxn];
int get_fa(int x) {
  if(p[x] == x) {
    return x;
  } else {
    return (p[x] = get_fa(p[x]));
  }
}
void link_set(int x, int y) {
  if(rk[x] > rk[y]) std::swap(x, y);
  p[x] = y;
  if(rk[x] == rk[y]) rk[y] ++;
}
void merge_set(int x, int y) {
  x = get_fa(x); y = get_fa(y);
  if(x != y) link_set(x, y);
}
bool is_same(int x, int y) {
  return (get_fa(x) == get_fa(y));
}
void init_set() {
  for(int i = 1; i <= n; i ++) {
    p[i] = i;
  }
}

struct Edge {
  int u, v; ll w;
  Edge(int a = 0, int b = 0, ll c = 0) {
    u = a; v = b; w = c;
  }
  bool operator <(const Edge &res) const {
    return w < res.w;
  }
};
int m; Edge E[maxm];
int ecnt;
void process() {
  dij(); ecnt = 0;
  for(int i = 1; i <= n; i ++) {
    for(int j = first[i]; j; j = next[j]) {
      int v = to[j];
      if(dir[j] && src[i] != src[v]) {
        E[++ ecnt] = Edge(src[i], src[v], (ll(dist[j])) + d[i] + d[v]);
      }
    }
  }
  std::sort(E + 1, E + 1 + ecnt);
}
bool ans[maxm];
void solve() {
  int q; scanf("%d", &q);
  init_set(); int cur = 0;
  std::vector<std::pair<Edge, int> > Q;
  for(int i = 1; i <= q; i ++) {
    int u, v; ll w; scanf("%d%d%lld", &u, &v, &w);
    Q.push_back(std::make_pair(Edge(u, v, w), i));
  }
  std::sort(Q.begin(), Q.end());
  for(auto x : Q) {
    Edge e = x.first;
    while(cur < ecnt && E[cur + 1].w <= e.w) {
      cur ++;
      merge_set(E[cur].u, E[cur].v);
    }
    ans[x.second] = is_same(e.u, e.v);
  }
  for(int i = 1; i <= q; i ++) {
    if(ans[i]) {
      puts("TAK");
    } else {
      puts("NIE");
    }
  }
}

int main() {
  int s; scanf("%d%d%d", &n, &s, &m);
  for(int i = 1; i <= s; i ++) {
    int x; scanf("%d", &x);
    V.push_back(x);
  }
  for(int i = 1; i <= m; i ++) {
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    ins_edge(u, v, w);
  }
  process(); solve();
  return 0;
}

• 相关文章
• 全局相关文章