题意:给你一张带权无向图,先求出这张图从点1出发的最短路树,再求在树上经过k个节点最长的路径值,以及个数.
分析:首先求最短路树,跑一遍最短路之后dfs一遍即可建出最短路树.
第二个问题,树分治解决.
对于以root为根的树,所求的路径只会有两种情况.
- 存在于root的子树中,不经过root;
- 经过root,路径的两端在root的两棵子树中.
第一种情况,我们交给分治去解决,
第二种情况,需要知道所有子树中走过j步能到达的最远距离,以及其方案数.通过dfs可以得到这些信息.用这些信息,再去和其他子树的信息结合,去更新答案.
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 1<<30;
const int MAXN = 1e5+5;
struct Edge{
int v,w,next;
}E[MAXN<<2];
int head[MAXN],tot , son[MAXN], Max[MAXN], siz[MAXN], dep[MAXN] ,now[MAXN];
LL cnt[MAXN], Maxcnt[MAXN] , ansnum;
int maxdep , clk, ansdep, minson;
bool vis[MAXN];
int root,N,M,k;
void init()
{
memset(vis,0,sizeof(vis));
memset(head,-1,sizeof(head));
tot = ansnum = clk = 0;
ansdep = 0;
}
void Add(int u,int v,int w){
E[tot] =(Edge){v,w,head[u]};
head[u] = tot++;
}
//求子树的重心
void getsize(int u, int fa)
{
siz[u] = 1;
for (int i = head[u]; i != -1; i = E[i].next)
{
int v = E[i].v;
if (v == fa || vis[v])
continue;
getsize(v, u);
siz[u] += siz[v];
}
}
void getroot(int u, int fa, int s)
{
int max1 = 0;
for (int i = head[u]; i != -1; i = E[i].next)
{
int v = E[i].v;
if (v == fa || vis[v])
continue;
getroot(v, u, s);
max1 = max(max1, siz[v]);
}
max1 = max(max1, s - siz[u]);
if (minson > max1)
{
minson = max1;
root = u;
}
}
void getMaxdep(int depp, int u, int fa)
{
maxdep = max(maxdep, depp);
for (int i = head[u]; i != -1; i = E[i].next)
{
int v = E[i].v;
if (v == fa || vis[v])
continue;
getMaxdep(depp + 1, v, u);
}
}
void getdep(int depp, int len, int u, int fa)
{
if (dep[depp] < len)
{
dep[depp] = len;
cnt[depp] = 1;
}
else if (dep[depp] == len)
cnt[depp]++;
if (depp >= k)
return;
for (int i = head[u]; i != -1; i = E[i].next)
{
int v = E[i].v;
if (v == fa || vis[v])
continue;
getdep(depp + 1, len + E[i].w, v, u);
}
}
void getans(int u)
{
vis[u] = 1;
for (int i = head[u]; i != -1; i = E[i].next){
int v = E[i].v;
if (vis[v]) continue;
minson = INF;
getsize(v, -1);
getroot(v, -1, siz[v]);
getans(root);
}
/*
求经过k个节点的最长路径,以及其方案数
答案可能有两种情况, 一是存在于u的子树中,这种情况交给分治处理
二是该路径经过了重心本身,在以下代码中处理
*/
clk++;
now[0] = clk;
dep[0] = 0 ,cnt[0] = 1;
Maxcnt[0] = 1, Max[0] = 0;
for (int i = head[u]; i != -1; i = E[i].next){
int v = E[i].v;
if (vis[v]) continue;
maxdep = -1;
//获取这棵子树的最大深度
getMaxdep(1, v, u);
for (int j = 0; j <= maxdep && j <= k; j++) dep[j] = -1;
//获取这棵子树中经过i个节点,所能走的最长距离以及方案数,
//分别记录在dep[i], 和cnt[i]中
getdep(1, E[i].w, v, u);
//根据当前信息和这棵子树的信息更新答案
for (int j = 0; j <= maxdep && j < k; j++){
int tmp = k - j - 1;
if (now[tmp] != clk)
continue;
if (ansdep < Max[tmp] + dep[j]){
ansdep = Max[tmp] + dep[j];
ansnum = Maxcnt[tmp] * cnt[j];
}
else if (ansdep == Max[tmp] + dep[j]){
ansnum += Maxcnt[tmp] * cnt[j];
}
}
//用这个子树的信息更新当前的信息
//Max[i]记录之前已经访问过的子树中,经过i个节点能走过的最长距离
//Maxcnt[i] 记录其方案数
for (int j = 1; j <= maxdep && j < k; j++){
if (now[j] != clk || Max[j] < dep[j]){
Max[j] = dep[j];
Maxcnt[j] = cnt[j];
now[j] = clk;
}
else if (now[j] == clk && Max[j] == dep[j]){
Maxcnt[j] += cnt[j];
}
}
}
vis[u] = 0;
}
///////////最短路树
struct Dij{
struct Edge{
int v, w;
bool operator < (const Edge & rhs) const{
return v<rhs.v;
}
};
vector<Edge> G[MAXN];
int N,d[MAXN];
bool vis[MAXN];
struct HeapNode{
int u,val;
bool operator < (const HeapNode & rhs) const{
return val>rhs.val;
}
};
void init(int N){
this -> N = N;
memset(vis,0,sizeof(vis));
for(int i=0;i<=N;++i) G[i].clear();
}
void AddEdge(int u,int v,int w){
G[u].push_back((Edge){v,w});
}
void dijkstra(int s){
for(int i=1;i<=N;++i){
sort(G[i].begin(),G[i].end());
}
for(int i=0;i<=N;++i) d[i] = INF;
d[s] = 0;
priority_queue< HeapNode > Q;
Q.push((HeapNode){s,0});
while(!Q.empty()){
HeapNode x = Q.top(); Q.pop();
if(vis[x.u]) continue;
vis[x.u] = 1;
int u = x.u, sz = G[u].size();
for(auto & e : G[u]){
int v = e.v;
if(d[v]> d[u]+e.w){
d[v] = d[u] + e.w;
Q.push((HeapNode){v,d[v]});
}
}
}
}
void dfs(int u,int fa){
vis[u] = true;
for(auto & e: G[u]){
int v= e.v;
if(v==fa || vis[v]) continue;
if(d[v]== d[u]+e.w){
Add(u,v,e.w);
Add(v,u,e.w);
dfs(v,u);
}
}
}
}G;
////////////////// main
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int T; scanf("%d",&T);
while(T--){
scanf("%d %d %d",&N, &M, &k);
G.init(N);
int u,v,w;
while(M--){
scanf("%d %d %d",&u, &v, &w);
G.AddEdge(u,v,w);
G.AddEdge(v,u,w);
}
G.dijkstra(1);
init(); //树的初始化
memset(G.vis,0,sizeof(G.vis));
G.dfs(1,-1); //建最短路径树
memset(now,-1,sizeof(now));
root = -1;
minson = INF;
getroot(1,-1,N);
getans(root);
printf("%d %lld\n",ansdep,ansnum);
}
return 0;
}