程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ1741——Tree 基於點的分治

POJ1741——Tree 基於點的分治

編輯：C++入門知識

POJ1741——Tree 基於點的分治

Tree Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 11229 Accepted: 3515

Description

Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.

Input

The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l.
The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

Sample Output

Source

LouTiancheng@POJ

這題要我們計算所有滿足距離之和小於等於k的點對的數目， n最大有10000，顯然O(n^2)的做法是行不通的，看了部分09年漆子超《分治算法在樹的路徑問題中的應用》，於是試著去理解這種做法，然後寫下了這篇博客。

顯然我們可以知道，這樣的點對可以分為2種
1) 經過樹的根
2)在某一棵子樹裡面

而2顯然可以遞歸處理，所以我們把目光放在1

我們設dist[i]表示點i到根的距離，那麼我們1要求的就是 dist[i] + dist[j] <= k && i,j 屬於不同的子樹，從論文中我們可以學到，把所要求的轉化為dist[i] + dist[j] <= k的所有點對減去dist[i] + dist[j] <= k && i,j處在同一個子樹裡的點對，這就是我們要求的東西

而統計點對數，我們可以在O(n)的時間內完成，操作就是給數組排個序，然後左邊，右邊分別移動下標，邊移動邊統計就OK了，復雜度O(n*logn)

接下來還有一個問題，如果這個樹是一條鏈，那麼每次去遞歸子樹，復雜度顯然會到達O(n^2)，所以這裡又要引出一個內容：樹的重心

樹的重心是這樣定義的：刪掉重心以後，樹被分為幾個部分，使得那幾個部分裡點最多的那個部分的點數最少

樹的重心我們可以通過樹形dp在O(n)時間裡求得，可以證明，如果每次都選取子樹的重心作為根，那麼遞歸次數最多不超過logn次，所以整個過程下來，復雜度是O(n*logn*logn)

先放上我的代碼吧，也是結合了網上各個前輩的做法的
PS：我還想在代碼下面寫點關於代碼理解的

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 10010;
const int inf = 0x3f3f3f3f;
int num[N];
int head[N];
int dist[N];
int dp[N];
bool vis[N];
struct node
{
	int weight;
	int next;
	int to;
}edge[N << 1];

int tot, root, n, k, size, res, ans;

void addedge(int from, int to, int weight)
{
	edge[tot].weight = weight;
	edge[tot].to = to;
	edge[tot].next = head[from];
	head[from] = tot++;
}

void get_root(int u, int fa)
{
	num[u] = 1;
	dp[u] = 0;
	for (int i = head[u]; ~i; i = edge[i].next)
	{
		int v = edge[i].to;
		if (v == fa || vis[v]) //-------------------------A
		{
			 continue;
		}
		get_root(v, u);
 		num[u] += num[v];
		dp[u] = max(dp[u], num[v]);
	}
	dp[u] = max(dp[u], size - num[u]);
	if (dp[u] < dp[root])
	{
		 root = u;
	}
}

void calc_dist(int u, int fa, int d)
{
	dist[res++] = d;
	for (int i = head[u]; ~i; i = edge[i].next)
	{
		int v = edge[i].to;
		if (v == fa || vis[v])//--------------------------B
		{
			continue;
		}
		calc_dist(v, u, d + edge[i].weight);
	}
}

int counts(int u, int d)
{
	res = 0;
	calc_dist(u, -1, d);
	int ans = 0;
	sort(dist, dist + res);
	int i = 0;
	int j = res - 1;
	while (i < j)
	{
		while (i < j && dist[i] + dist[j] > k)
		{
		       j--;
		}
		ans += j - i;
		i++;
	}
	return ans;
}

void solve(int u)
{
	ans += counts(root, 0);
	vis[root] = 1;
	for (int i = head[root]; ~i; i = edge[i].next)
	{
		int v = edge[i].to;
		if (vis[v])
		{
			continue;
		}
		ans -= counts(v, edge[i].weight); // ------------------------------C
		root = 0;
		dp[0] = size = num[v];
 		get_root(v, -1);
		solve(v);
 	}
}

int main()
{
	 int u, v, w;
	 while (~scanf("%d%d", &n, &k))
	 {
		if (!n && !k)
		{
	         	break;
                }
		memset ( head, -1, sizeof(head) );
		memset ( num, 0, sizeof(num) );
		memset ( vis, 0, sizeof(vis) );
		tot = 0;
	        ans = 0;
		for (int i = 0; i < n - 1; ++i)
		{ 
 			scanf("%d%d%d", &u, &v, &w);
 			addedge(u, v, w);
			addedge(v, u, w);
		}
 		root = 0;
		dp[root] = size = n;
		get_root(1, -1);
 		solve(1);
 		printf("%d\n", ans);
 	}
 	return 0;
}

先來解釋下注釋C吧，

ans -= counts(v, edge[i].weight);

為什麼是edge[i].weight而不是0，今天看的時候不知道是不是腦子短路了一直沒理解，其實是這樣的，root(當前樹根)這棵樹統計完了點對以後，其實已經包含了某些點對，它們處在同一個子樹裡，但是距離和確實小於等於k的，那麼這裡小於等於k是基於它們到點root的，所以在處理v這個子樹的時候，我們需要把這樣的點對給去掉，那麼基准點當然還是以root為主，這樣才能准確地去掉這些點對，所以要加上root --- v這條邊上的權值

再來看A和B，為什麼要加一個fa，由於建立的是無向邊，所以得加一個fa，放止從子樹跑到根上去
vis數組是為了防止訪問到已經處理過的重心（子樹的根），我們每次找到一個重心，要拿它當根來處理的時候，都會把它標記為已經訪問過，如果不慎訪問到了已經訪問過的root（即子樹），那麼分治就被干擾了，或者說已經被破壞了，所以這個vis數組是一定要加上去的
基本就講到這裡，如果發現本人所寫有錯誤，歡迎給我留言