HDU 4871 Shortest-path tree （树分治）

HDU 4871

Shortest-path tree

树分治。  

Shortest-path tree

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 130712/130712 K (Java/Others) Total Submission(s): 146 Accepted Submission(s): 47

Problem Description

Given a connected, undirected graph G, a shortest-path tree rooted at vertex v is a spanning tree T of G, such that the path distance from root v to any other vertex u in T is the shortest path distance from v to u in G. We may construct a shortest-path tree using the following method: We consider a shortest-path tree rooted at node 1. For every node i in the graph G, we choose a shortest path from root to i. If there are many shortest paths from root to i, we choose the one that the sequence of passing nodes’ number is lexicographically minimum. All edges on the paths that we chose form a shortest-path tree. Now we want to know how long are the longest simple paths which contain K nodes in the shortest-path tree and how many these paths? Two simple paths are different if the sets of nodes they go through are different.

Input

The first line has a number T (T <= 10), indicating the number of test cases. For each test case, the first line contains three integers n, m, k(1<=n<=30000,1<=m<=60000,2<=k<=n), denote the number of nodes, the number of edges and the nodes of required paths. Then next m lines, each lines contains three integers a, b, c(1<=a, b<=n, 1<=c<=10000),denote there is an edge between a, b and length is c.

Output

For each case, output two numbers, denote the length of required paths and the numbers of required paths.

Sample Input

1 6 6 4 1 2 1 2 3 1 3 4 1 2 5 1 3 6 1 5 6 1

Sample Output

3 4

Author

FZU

Source

2014 Multi-University Training Contest 1

首先跑一下堆优化的Dij 或者SPFA 把树搞出来。   树搞出来以后就是树分治了。 一颗一颗子树加入。每次都找重心。 树分治写起来要小心，很容易T的。 树分治还需要多练习了。

/* ***************

Author        :kuangbin

Created Time  :2014/7/23 17:45:13

File Name     :E:\2014ACM\比赛\2014多校训练\2014多校1\HDU4871.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int INF = 0x3f3f3f3f;

const int MAXN = 30010;

struct qnode

{

	int v;

	int c;

	qnode(int _v = 0,int _c = 0):v(_v),c(_c){}

	bool operator <(const qnode &r)const

	{

		if(c != r.c)return c > r.c;

		else return v > r.v;

	}

};

struct EE

{

	int v,cost;

	EE(int _v = 0,int _cost = 0):v(_v),cost(_cost){}

};

vector<EE>E[MAXN];

bool vis[MAXN];

int dist[MAXN];

int pre[MAXN];

int pre_w[MAXN];

void Dijkstra(int n,int start)

{

	memset(vis,false,sizeof(vis));

	for(int i = 1;i <= n;i++)dist[i] = INF;

	priority_queue<qnode>que;

	while(!que.empty())que.pop();

	dist[start] = 0;

	pre[start] = -1;

	que.push(qnode(start,0));

	qnode tmp;

	while(!que.empty())

	{

		tmp = que.top();

		que.pop();

		int u = tmp.v;

		if(vis[u])continue;

		vis[u] = true;

		for(int i = 0;i < E[u].size();i++)

		{

			int v = E[u][i].v;

			int cost = E[u][i].cost;

			if(!vis[v])

			{

				if(dist[v] > dist[u]+cost)

				{

					dist[v] = dist[u]+cost;

					pre[v] = u;

					pre_w[v] = E[u][i].cost;

					que.push(qnode(v,dist[v]));

				}

				else if(dist[v] == dist[u]+cost && u < pre[v])

				{

					pre[v] = u;

					pre_w[v] = cost;

				}

			}

		}

	}

}

struct Edge

{

	int to,next;

	int w;

}edge[MAXN*2];

int head[MAXN],tot;

void init()

{

	memset(head,-1,sizeof(head));

	tot = 0;

}

void addedge(int u,int v,int w)

{

	edge[tot].to = v;

	edge[tot].w = w;

	edge[tot].next = head[u];

	head[u] = tot++;

}

int ans1,ans2;

int k;

int size[MAXN];

int dfssize(int u,int pre)

{

	size[u] = 1;

	for(int i = head[u];i != -1;i = edge[i].next)

	{

		int v = edge[i].to;

		if(v == pre || vis[v])continue;

		size[u] += dfssize(v,u);

	}

	return size[u];

}

int minn;

void getroot(int u,int pre,int totnum,int &root)

{

	int maxx = totnum - size[u];

	for(int i = head[u];i != -1;i = edge[i].next)

	{

		int v = edge[i].to;

		if(v == pre || vis[v])continue;

		getroot(v,u,totnum,root);

		maxx = max(maxx,size[v]);

	}

	if(maxx < minn){minn = maxx; root = u;}

}

int dp[MAXN];

int dpnum[MAXN];

int pd[MAXN];

int pdnum[MAXN];

bool used[MAXN];

int dis[MAXN];

int dep[MAXN];

int maxdep;

void getdp(int s,int w)

{

	memset(pd,0,sizeof(pd));

	memset(pdnum,0,sizeof(pdnum));

	memset(used,false,sizeof(used));

	pdnum[0] = 1;

	dis[s] = w;

	dep[s] = 1;

	pd[dep[s]] = w;

	pdnum[dep[s]] = 1;

	queue<int>q;

	q.push(s);

	used[s] = true;

	while(!q.empty())

	{

		int u = q.front();

		q.pop();

		if(maxdep < dep[u])maxdep = dep[u];

		for(int i = head[u];i != -1;i = edge[i].next)

		{

			int v = edge[i].to;

			if(used[v] || vis[v])continue;

			dep[v] = dep[u]+1;

			dis[v] = dis[u]+edge[i].w;

			used[v] = true;

			q.push(v);

			if(dis[v] > pd[dep[v]])

			{

				pd[dep[v]] = dis[v];

				pdnum[dep[v]] = 1;

			}

			else if(dis[v] == pd[dep[v]])

				pdnum[dep[v]]++;

		}

	}

}

void getpd(int u,int pre,int nw,int nd)

{

	if(nd > k-1)return;

	if(maxdep < nd)maxdep = nd;

	if(nw > pd[nd])

	{

		pd[nd] = nw;

		pdnum[nd] = 1;

	}

	else if(nw == pd[nd])

		pdnum[nd]++;

	for(int i = head[u];i != -1;i = edge[i].next)

	{

		int v = edge[i].to;

		if(v == pre || vis[v])continue;

		getpd(v,u,nw+edge[i].w,nd+1);

	}

}

void solve(int u)

{

	int totnum = dfssize(u,-1);

	minn = INF;

	int root;

	getroot(u,-1,totnum,root);

	vis[root] = true;

	for(int i = 0;i <= totnum;i++)

	{

		dp[i] = 0;

		dpnum[i] = 0;

	}

	dpnum[0] = 1;

	for(int i = head[root];i != -1;i = edge[i].next)

	{

		int v = edge[i].to;

		if(vis[v])continue;

		maxdep = 0;

		for(int j = 0;j <= size[v];j++)

		{

			pd[j] = 0;

			pdnum[j] = 0;

		}

		pdnum[0] = 1;

		getpd(v,u,edge[i].w,1);

		for(int j = 1;j <= maxdep && j < k;j++)

			if(pdnum[j]&&dpnum[k-1-j])

			{

				if(ans1 < pd[j]+dp[k-1-j])

				{

					ans1 = pd[j]+dp[k-1-j];

					ans2 = pdnum[j]*dpnum[k-1-j];

				}

				else if(ans1 == pd[j]+dp[k-1-j])

					ans2 += pdnum[j]*dpnum[k-1-j];

			}

		for(int j = 1;j <= maxdep && j <= k;j++)

		{

			if(dp[j] < pd[j])

			{

				dp[j] = pd[j];

				dpnum[j] = pdnum[j];

			}

			else if(dp[j] == pd[j])

				dpnum[j] += pdnum[j];

		}

	}

	for(int i = head[root];i != -1;i = edge[i].next)

	{

		int v = edge[i].to;

		if(vis[v])continue;

		solve(v);

	}

}

int main()

{

    //freopen("1011.in","r",stdin);

    //freopen("out.txt","w",stdout);

    int T;

	int n,m;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d%d",&n,&m,&k);

		for(int i = 1;i <= n;i++)E[i].clear();

		int u,v,w;

		while(m--)

		{

			scanf("%d%d%d",&u,&v,&w);

			E[u].push_back(EE(v,w));

			E[v].push_back(EE(u,w));

		}

		Dijkstra(n,1);

		init();

		int ccc = 0;

		for(int i = 2;i <= n;i++)

		{

			addedge(i,pre[i],pre_w[i]);

			addedge(pre[i],i,pre_w[i]);

		}

		ans1 = 0; ans2 = 0;

		memset(vis,false,sizeof(vis));

		solve(1);

		printf("%d %d\n",ans1,ans2);

	}

    return 0;

}