[BZOJ4016][FJOI2014]最短路径树问题
试题描述
给一个包含n个点，m条边的无向连通图。从顶点1出发，往其余所有点分别走一次并返回。
往某一个点走时，选择总长度最短的路径走。若有多条长度最短的路径，则选择经过的顶点序列字典序最小的那条路径(如路径A为1,32,11，路径B为1,3,2,11，路径B字典序较小。注意是序列的字典序的最小，而非路径中节点编号相连的字符串字典序最小)。到达该点后按原路返回，然后往其他点走，直到所有点都走过。
可以知道，经过的边会构成一棵最短路径树。请问，在这棵最短路径树上，最长的包含K个点的简单路径长度为多长？长度为该最长长度的不同路径有多少条？
这里的简单路径是指：对于一个点最多只经过一次的路径。不同路径是指路径两端端点至少有一个不同，点A到点B的路径和点B到点A视为同一条路径。
输入
第一行输入三个正整数n,m，K，表示有n个点m条边，要求的路径需要经过K个点。接下来输入m行，每行三个正整数Ai,Bi,Ci(1<=Ai,Bi<=n,1<=Ci<=10000)，表示Ai和Bi间有一条长度为Ci的边。数据保证输入的是连通的无向图。
输出
输出一行两个整数，以一个空格隔开，第一个整数表示包含K个点的路径最长为多长，第二个整数表示这样的不同的最长路径有多少条。
输入示例
6 6 4 1 2 1 2 3 1 3 4 1 2 5 1 3 6 1 5 6 1
输出示例
3 4
数据规模及约定
对于所有数据n<=30000,m<=60000，2<=K<=n。数据保证最短路径树上至少存在一条长度为K的路径。
题解
对于每一个点的出边按照目标点编号从小到大排序，跑一边 Dijkstra，构造出树，再套点分治。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 30010
#define maxm 60010
#define oo 2147483647
int n, m, M, K;
struct Edge {
int v, w;
Edge() {}
Edge(int _, int __): v(_), w(__) {}
bool operator < (const Edge& t) const { return v < t.v; }
} ;
vector <Edge> E[maxn];
bool vis[maxn];
int d[maxn], fa[maxn], fad[maxn];
struct Node {
int u, d;
Node() {}
Node(int _, int __): u(_), d(__) {}
bool operator < (const Node& t) const { return d > t.d; }
} ;
priority_queue <Node> Q;
void Dijkstra() {
for(int i = 1; i <= n; i++) d[i] = oo;
d[1] = 0;
Q.push(Node(1, 0));
while(!Q.empty()) {
int u = Q.top().u; Q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i = 0; i < E[u].size(); i++)
if(d[E[u][i].v] > d[u] + E[u][i].w) {
d[E[u][i].v] = d[u] + E[u][i].w;
fa[E[u][i].v] = u; fad[E[u][i].v] = E[u][i].w;
if(!vis[E[u][i].v]) Q.push(Node(E[u][i].v, d[E[u][i].v]));
}
}
return ;
}
int head[maxn], to[maxm], next[maxm], dist[maxm];
void AddEdge(int a, int b, int c) {
to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;
return ;
}
int root, size, siz[maxn], f[maxn], ans, ansc;
void getroot(int u, int pa) {
siz[u] = 1; f[u] = 0;
for(int e = head[u]; e; e = next[e]) if(!vis[to[e]] && to[e] != pa) {
getroot(to[e], u);
siz[u] += siz[to[e]];
f[u] = max(f[u], siz[to[e]]);
}
f[u] = max(f[u], size - siz[u]);
if(f[u] < f[root]) root = u;
return ;
}
int A[maxn], Ac[maxn], B[maxn], Bc[maxn], mxd;
void dfs(int u, int d, int dep, int pa) {
mxd = max(mxd, dep);
// printf("XXX: %d %d %d
", u, d, dep);
if(!Ac[dep] || A[dep] < d) A[dep] = d, Ac[dep] = 1;
else if(A[dep] == d) Ac[dep]++;
for(int e = head[u]; e; e = next[e]) if(!vis[to[e]] && to[e] != pa)
dfs(to[e], d + dist[e], dep + 1, u);
return ;
}
void solve(int u) {
// printf("u: %d
", u);
vis[u] = 1;
int Mxd = 0;
for(int e = head[u]; e; e = next[e]) if(!vis[to[e]]) {
mxd = 0;
dfs(to[e], dist[e], 1, u);
Mxd = max(Mxd, mxd);
Ac[0] = Bc[0] = 1;
// for(int i = 1; i <= mxd; i++) printf("here: %d(%d) ", A[i], Ac[i]); putchar('
');
for(int i = 1; i <= min(K, mxd); i++)
if(!ansc || ans < A[i] + B[K-i]) ans = A[i] + B[K-i], ansc = Ac[i] * Bc[K-i];
else if(ans == A[i] + B[K-i]) ansc += Ac[i] * Bc[K-i];
for(int i = 1; i <= mxd; i++) {
if(!Bc[i] || B[i] < A[i]) B[i] = A[i], Bc[i] = Ac[i];
else if(B[i] == A[i]) Bc[i] += Ac[i];
A[i] = Ac[i] = 0;
}
}
for(int i = 1; i <= Mxd; i++) B[i] = Bc[i] = 0;
for(int e = head[u]; e; e = next[e]) if(!vis[to[e]]) {
root = 0; f[0] = n + 1; size = siz[u]; getroot(to[e], u);
solve(root);
}
return ;
}
int main() {
n = read(); M = read(); K = read() - 1;
for(int i = 1; i <= M; i++) {
int a = read(), b = read(), c = read();
E[a].push_back(Edge(b, c)); E[b].push_back(Edge(a, c));
}
for(int i = 1; i <= n; i++) sort(E[i].begin(), E[i].end());
Dijkstra();
for(int i = 2; i <= n; i++) AddEdge(i, fa[i], fad[i]);
// for(int i = 1; i <= n; i++) printf("%d ", fa[i]); putchar('
');
memset(vis, 0, sizeof(vis));
root = 0; f[0] = n + 1; size = n; getroot(1, 0);
solve(root);
printf("%d %d
", ans, ansc);
return 0;
}
简直是强行乱套