FJOI2014 最短路径树问题

未分类

将最短路树建出来，点分治就行了。

因为最大值不能直接容斥，所以每次分别计算子树的贡献。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
const int MAXN = 3e4;
const int MAXM = 6e4;
int n, m, K, edge1, edge2, allSize, root, ans1, ans2;
int fst1[MAXN | 1], fst2[MAXN | 1];
int f[MAXN | 1], size[MAXN | 1];
int maxx[MAXN | 1], sumx[MAXN | 1];
bool vis[MAXN | 1];
struct E {
  int u, v, w;
  E() : u(0), v(0), w(0) {}
  E(int x, int y, int z) : u(x), v(y), w(z) {}
} a[MAXM | 1];
inline bool comp1(const E &lhs, const E &rhs) {
  return lhs.v > rhs.v;
}
inline bool comp2(const E &lhs, const E &rhs) {
  return lhs.u > rhs.u;
}
struct Edge {
  int to, w, nxt;
  Edge() : to(0), w(0), nxt(0) {}
  Edge(int a, int b, int c) : to(b), w(c), nxt(a) {}
} e1[MAXM << 1 | 1], e2[MAXM << 1 | 1];
struct Heap {
  int x, dis;
  Heap() : x(0), dis(0) {}
  Heap(int a, int b) : x(a), dis(b) {}
  friend bool operator< (const Heap &lhs, const Heap &rhs) {
    return lhs.dis > rhs.dis;
  }
};
inline int read() {
  register int x = 0; 
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
void Dijkstra() {
  std::priority_queue < Heap > q;
  int dist[MAXN | 1];
  memset(dist, 0x3f, sizeof(dist));
  dist[1] = 0;
  q.push(Heap(1, 0));
  do {
    Heap from = q.top();
    q.pop();
    if (from.dis != dist[from.x]) continue;
    for (int k = fst1[from.x]; k; k = e1[k].nxt) {
      int to = e1[k].to, w = e1[k].w;
      if (dist[to] > dist[from.x] + w) {
        dist[to] = dist[from.x] + w;
        q.push(Heap(to, dist[to]));
      }
    }
  } while (!q.empty());
  std::queue < int > qq;
  qq.push(1);
  do {
    int from = qq.front();
    qq.pop();
    for (int k = fst1[from]; k; k = e1[k].nxt) {
      int to = e1[k].to, w = e1[k].w;
      if (dist[to] == dist[from] + w && !vis[to]) {
        vis[to] = 1;
        e2[++edge2] = Edge(fst2[from], to, w);
        fst2[from] = edge2;
        e2[++edge2] = Edge(fst2[to], from, w);
        fst2[to] = edge2;
        qq.push(to);
      }
    }
  } while (!qq.empty());
}
void getRoot(int x, int fa) {
  size[x] = 1;
  f[x] = 0;
  for (int k = fst2[x]; k; k = e2[k].nxt) {
    int to = e2[k].to;
    if (to == fa || vis[to]) continue;
    getRoot(to, x);
    size[x] += size[to];
    f[x] = std::max(f[x], size[to]);
  }
  f[x] = std::max(f[x], allSize - size[x]);
  if (f[x] < f[root] || root == 0) root = x;
}
void getSonAns(int x, int fa, int ww, int depth) {
  if (depth >= K) return;
  if (maxx[K - 1 - depth] + ww > ans1) {
    ans1 = maxx[K - 1 - depth] + ww;
    ans2 = sumx[K - 1 - depth];
  } else if (maxx[K - 1 - depth] + ww == ans1) ans2 += sumx[K - 1 - depth];
  for (int k = fst2[x]; k; k = e2[k].nxt) {
    int to = e2[k].to, w = e2[k].w;
    if (to == fa || vis[to]) continue;
    getSonAns(to, x, ww + w, depth + 1);
  }
}
void getDis(int x, int fa, int ww, int depth) {
  if (depth >= K) return;
  if (ww > maxx[depth]) {
    maxx[depth] = ww;
    sumx[depth] = 1;
  } else if (ww == maxx[depth]) ++sumx[depth];
  for (int k = fst2[x]; k; k = e2[k].nxt) {
    int to = e2[k].to, w = e2[k].w;
    if (to == fa || vis[to]) continue;
    getDis(to, x, ww + w, depth + 1);
  }
}
void remove(int x, int fa, int ww, int depth) {
  if (depth >= K) return;
  maxx[depth] = 0;
  sumx[depth] = 0;
  for (int k = fst2[x]; k; k = e2[k].nxt) {
    int to = e2[k].to, w = e2[k].w;
    if (to == fa || vis[to]) continue;
    remove(to, x, ww + w, depth + 1);
  }
}
void getAns(int x) {
  maxx[0] = 0;
  sumx[0] = 1;
  for (int k = fst2[x]; k; k = e2[k].nxt) {
    int to = e2[k].to, w = e2[k].w;
    if (!vis[to]) {
      getSonAns(to, x, w, 1);
      getDis(to, x, w, 1);
    }
  }
  for (int k = fst2[x]; k; k = e2[k].nxt) {
    int to = e2[k].to, w = e2[k].w;
    if (!vis[to]) remove(to, x, w, 1);
  }
}
void DAC(int x) {
  vis[x] = 1;
  getAns(x);
  // printf("ffffrom=%d ans1=%d ans2=%d\n", x, ans1, ans2);
  int lstSize = allSize;
  for (int k = fst2[x]; k; k = e2[k].nxt) {
    int to = e2[k].to;
    if (vis[to]) continue;
    allSize = size[to] > size[x] ? lstSize - size[x] : size[to];
    root = 0;
    getRoot(to, x);
    DAC(root);
  }
}
int main() {
  n = read();
  m = read();
  K = read();
  for (int i = 1; i <= m; ++i) {
    a[i].u = read();
    a[i].v = read();
    a[i].w = read();
  }
  std::sort(a + 1, a + m + 1, comp1);
  for (int i = 1; i <= m; ++i) {
    e1[++edge1] = Edge(fst1[a[i].u], a[i].v, a[i].w);
    fst1[a[i].u] = edge1;
  }
  std::sort(a + 1, a + m + 1, comp2);
  for (int i = 1; i <= m; ++i) {
    e1[++edge1] = Edge(fst1[a[i].v], a[i].u, a[i].w);
    fst1[a[i].v] = edge1;
  }
  Dijkstra();
  allSize = n;
  memset(vis, 0, sizeof(vis));
  getRoot(1, 0);
  DAC(root);
  printf("%d %d\n", ans1, ans2);
  return 0;
}