[BZOJ4016][FJOI2014]最短路径树问题

时间：2022-08-07 17:20:40

[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个点的路径最长为多长，第二个整数表示这样的不同的最长路径有多少条。

输入示例





输出示例




 




数据规模及约定


对于所有数据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\n", 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\n", 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('\n');

		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('\n');

	memset(vis, 0, sizeof(vis));

	root = 0; f[0] = n + 1; size = n; getroot(1, 0);

	solve(root);

	printf("%d %d\n", ans, ansc);

	return 0;

}





简直是强行乱套
相关文章