Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

参考网上写的带详细注释版的代码,希望给看不懂网上解题报告的人一点启发

Posted by zoujing1978 at 2019-07-08 02:09:16 on Problem 3728
/*
Description
n个城市构成一棵树,每个城市都有一种商品有一个固定的价格,一个商人要从一个城市到另一个城市,
他会在路途中选取一个城市购买这种商品然后在之后的某个城市卖掉以赚取差价,求最大差价。
Input
第一行一整数n表示城市个数,之后n个整数val[i]表示第i个城市该种商品的价格,之后n-1行每行两个整数u和v表示u城市和v城市有路径,
然后输入一整数q表示查询数,每次查询输入两个整数u和v表示商人从u到v路途中可以赚取的最大差价(1<=n,val[i],q<=50000)
Output
对于每组查询输出一个答案
Sample Input
4
1
5
3
2
1 3
3 2
3 4
9
1 2
1 3
1 4
2 3
2 1
2 4
3 1
3 2
3 4
Sample Output
4
2
2
0
0
0
0
2
0
思路:
p[i][j]表示i节点的第2^j层的祖先节点,maxVal[i][j]、minVal[i][j]分别表示i节点到i节点往上2^j个节点的路径上点权值最大值和最小值,
up[i][j]表示节点i到节点i往上走2^j条边对应路径上可以赚取的最大差价,down[i][j]表示节点i往上2^j层的祖先节点到节点i路径上可以赚取的最大差价,
LCA(u,v)表示点u和点v的最近公共祖先节点,那么从u到v的路径上可以赚取的路径最大值有3种情况:
1.从u到LCA(u,v)的up值,即买和卖都发生在节点u到LCA(u,v)对应路径上;
2.LCA(u,v)到v的maxVal减去从u到LCA(u,v)的minVal,即买和卖都发生在节点u到LCA(u,v)对应路径上,卖发生在LCA(u,v)到节点v对应路径上;
3.LCA(u,v)到v的down值,即买和卖都发生在LCA(u,v)到节点v对应路径上。
选取一个最大值即为答案。
*/

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cfloat>
using namespace std;

struct VerInfo				// 树中的顶点类型
{
	double val;
	list<int> arcs;
};

// 经测试,此题对每一个测试用例使用动态内存分配会超时,故使用全局大数据
int deep[50005];			// deep[i]表示节点i的深度
VerInfo vertex[50005];		// 邻接表顶点数组
int p[50005][17];			// p[i][j]表示节点i网上往上2^j层的祖先节点编号,2^16>50005,2^15<50005
double down[50005][17];		// down[i][j]表示节点i往上2^j层对应的祖先节点到i路径上可以赚取的最大差价
double up[50005][17];		// up[i][j]表示i节点到i节点往上2^j层对应的节点路径上可以赚取的最大差价
double maxVal[50005][17];	// maxVal[i][j]表示节点i往上2^j层对应的祖先节点到i路径上的最大值
double minVal[50005][17];	// minVal[i][j]表示i节点到i节点往上2^j层对应的节点路径上的最小值

class Merchant
{
protected:
	int n;				// 树中的节点数
	//int* deep;		// deep[i]表示节点i的深度
	//VerInfo* vertex;
	//int temp;
	//int** p;			// p[i][j]表示节点i网上往上2^j层的祖先节点编号
	//double** down;	// down[i][j]表示节点往上2^j节点到i路径上可以赚取的最大差价
	//double** up;		// up[i][j]表示i节点到i节点往上2^j节点路径上可以赚取的最大差价
	//double** maxVal;	// maxVal[i][j]表示节点i往上2^j层对应的祖先节点到i路径上的最大值
	//double** minVal;	// minVal[i][j]表示i节点到i节点往上2^j层对应的节点路径上的最小值
	void DFS(int u, int father);	// 搜索以u为根的子树,father是u的父节点
	void Init();		// // 初始化,计算deep数组、p数组、maxVal数组、minVal数组、up数组、down数组
	int LCA(int a, int b);			// 查找点a和点b的最近公共祖先
	double QueryDown(int x, int k, double& max_val);	// 计算点x向上k层的祖先节点到节点x的路径上能赚取的最大差价,以及顶点的最大权值max_val
	double QueryUp(int x, int k, double& min_val);		// 计算点x向上走k层的路径上能赚取的最大差价,以及顶点的最小权值min_val
	//void AllocMem();
	//void FreeMem();
public:
	void Solve();
};

//void Merchant::AllocMem()
//{
//	vertex = new VerInfo[n];
//	deep = new int[n];
//	//temp = (int)log((double)n) + 3;
//	temp = 20;
//	down = new double* [n];
//	for (int i = 0; i < n; i++)
//	{
//		down[i] = new double[temp];
//	}
//	up = new double* [n];
//	for (int i = 0; i < n; i++)
//	{
//		up[i] = new double[temp];
//	}
//	maxVal = new double* [n];
//	for (int i = 0; i < n; i++)
//	{
//		maxVal[i] = new double[temp];
//	}
//	minVal = new double* [n];
//	for (int i = 0; i < n; i++)
//	{
//		minVal[i] = new double[temp];
//	}
//	p = new int* [n];
//	for (int i = 0; i < n; i++)
//	{
//		p[i] = new int[temp];
//	}
//}

//void Merchant::FreeMem()
//{
//	for (int i = 0; i < n; i++)
//	{
//		delete[] p[i];
//	}
//	delete[] p;
//	for (int i = 0; i < n; i++)
//	{
//		delete[] maxVal[i];
//	}
//	delete[] maxVal;
//	for (int i = 0; i < n; i++)
//	{
//		delete[] minVal[i];
//	}
//	delete[] minVal;
//	for (int i = 0; i < n; i++)
//	{
//		delete[] up[i];
//	}
//	delete[] up;
//	for (int i = 0; i < n; i++)
//	{
//		delete[] down[i];
//	}
//	delete[] down;
//	delete[] deep;
//	for (int i = 0; i < n; i++)
//	{
//		vertex[i].arcs.clear();
//	}
//	delete[] vertex;
//}

// 搜索以u为根的子树,father是u的父节点
void Merchant::DFS(int u, int father)
{
	// 从u点出发,遍历u能到达的点*i
	for (list<int>::iterator i = vertex[u].arcs.begin(); i != vertex[u].arcs.end(); i++)
	{
		int v = *i;
		if (v == father)	// 避免走回头路
		{
			continue;
		}
		deep[v] = deep[u] + 1;	// 计算深度
		p[v][0] = u;			// 表示v向上走一步到达u
		maxVal[v][0] = max(vertex[u].val, vertex[v].val);		// 计算从点v往上的1个点到v的路径经过的点的最大权值
		minVal[v][0] = min(vertex[u].val, vertex[v].val);		// 计算从点v到往上的1个点的路径经过的点的最小权值
		down[v][0] = max(0.0, vertex[v].val - vertex[u].val);	// 计算从点v往上的1个点到v的路径可以赚取的最大差价
		up[v][0] = max(0.0, vertex[u].val - vertex[v].val);		// 计算从点v到往上的1个点的路径可以赚取的最大差价
		DFS(v, u);				// 递归,从v开始搜索
	}
}

// 初始化,计算deep数组、p数组、maxVal数组、minVal数组、up数组、down数组
void Merchant::Init()
{
	deep[0] = 1;					// 以点0作为根节点,深度为1
	for (int i = 0; i < n; i++)		// p数组置为-1,表示每个节点的父节点还没计算
	{
		fill(p[i], p[i] + 20, -1);
	}
	DFS(0, -1);						// 搜索以点0为根的子树,-1表示点0没有父节点
	for (int j = 1; (1 << j) <= n; j++)	// j表示遍历所有向上走的2的幂数的步数,即枚举出从点i向上走2^j条边对应的路径
	{
		for (int i = 0; i < n; i++)		// 枚举每一个点
		{
			if (p[i][j - 1] != -1)		// 如果点i向上走2^(j-1)条边能到达某个祖先点
			{
				int k = p[i][j - 1];	// k表示点i向上走2^(j-1)条边到达的祖先点
				p[i][j] = p[k][j - 1];	// 显然,点i向上走2^j条边到达的祖先点,就是k向上走2^(j-1)条边到达的祖先点
				maxVal[i][j] = max(maxVal[i][j - 1], maxVal[k][j - 1]);		// 计算点i向上2^j层对应的祖先点到点i沿途经过的点的最大权值
				minVal[i][j] = min(minVal[i][j - 1], minVal[k][j - 1]);		// 计算点i向上走2^j条边沿途经过的点的最小权值
				// 节点i往上2^j层对应的祖先节点到i路径上可以赚取的最大差价,有3种可能:
				// (1)卖发生在点k到点i这条路径上,买发生在点k向上到点i走2^(j-1)条边对应的祖先节点到k这条路径上;
				// (2)买和卖都出现在点k到点i这条路径上;
				// (3)买和卖都出现在点k向上走2^(j-1)条边对应的祖先节点到k这条路径上
				// 对于(1),假设从点i向上走2^j条边沿途经过的点,最大值在点i向上走2^(j-1)条边(即到达点k)这条路径上,最小值在点k向上走2^(j-1)条边这条路径上,计算点i向上走2^j条边能赚取的差价的最大值a
				double a = max(0.0, maxVal[i][j - 1] - minVal[k][j - 1]);
				// 对于(2),如果买和卖都出现在点k到点i这条路径上,则能赚取的最大差价为down[i][j - 1],对于(3),如果买和卖都出现在点k向上走2^(j-1)条边对应的祖先节点到k这条路径上,则能赚取的最大差价为down[k][j - 1],取两者较大值b
				double b = max(down[i][j - 1], down[k][j - 1]);
				// 显然,节点i往上2^j层对应的祖先节点到i路径上可以赚取的最大差价为a和b的较大值
				down[i][j] = max(a, b);
				// 节点i往上走2^j层的路径上可以赚取的最大差价,有3种可能:
				// (1)买发生在点k到点i这条路径上,卖发生在点k向上到点i走2^(j-1)条边对应的祖先节点到k这条路径上;
				// (2)买和卖都出现在点k到点i这条路径上;
				// (3)买和卖都出现在点k向上走2^(j-1)条边到达的祖先节点这条路径上
				// 对于(1),假设从点i向上走2^j条边沿途经过的点,最大值在点k向上走2^(j-1)条边这条路径上,最小值在点i向上走2^(j-1)条边(即到达点k)这条路径上,计算点i向上2^j条边对应的祖先节点到点i能赚取的差价的最大值a
				a = max(0.0, maxVal[k][j - 1] - minVal[i][j - 1]);
				// 对于(2),如果买和卖都出现在点i到点k这条路径上,则能赚取的最大差价为up[i][j - 1],对于(3),如果买和卖都出现在点k向上走2^(j-1)条边对应的路径上,则能赚取的最大差价为up[k][j - 1],取两者较大值b
				b = max(up[i][j - 1], up[k][j - 1]);
				// 显然,节点i往上走2^j层的i路径上可以赚取的最大差价为a和b的较大值
				up[i][j] = max(a, b);
			}
		}
	}
}

// 查找点a和点b的最近公共祖先节点
int Merchant::LCA(int a, int b)
{
	if (deep[a] < deep[b])	// 保持点a和点b中的深度较深者为a
	{
		swap(a, b);
	}
	// 计算一个i值,当a向上走2^i条边没有到达根节点,但是向上走2^(i+1)条边会到达根节点甚至越过根节点
	int i = 0;
	while ((1 << (i + 1)) <= deep[a])
	{
		i++;
	}
	// 点a每次向上走2的某个幂数条边(按照2的幂数递减顺序),直到点a和点b在同一深度
	for (int j = i; j >= 0; j--)
	{
		if (deep[a] - (1 << j) >= deep[b])
		{
			a = p[a][j];
		}
	}
	// 如果点a每次向上走2的某个幂数条边,直到点a和点b在同一深度时,正好和点b重合,则点b就是点a和点b的最近公共祖先
	if (a == b)
	{
		return a;
	}
	// 点a和点b同时向上走2的某个幂数条边(按照2的幂数递减顺序),直到双方如果再向上走1步就重合
	for (int j = i; j >= 0; j--)
	{
		if (p[a][j] != -1 && p[a][j] != p[b][j])
		{
			a = p[a][j];
			b = p[b][j];
		}
	}
	// 此时点a和点b的最近公共祖先显然是点a的父节点
	return p[a][0];
}

// 计算点x向上k层的祖先节点到节点x的路径上能赚取的最大差价,以及顶点的最大权值max_val
double Merchant::QueryDown(int x, int k, double& max_val)
{
	double ans = 0;	// ans表示点x向上2^k层的祖先节点到节点x的路径上能赚取的最大差价
	max_val = DBL_MIN;
	for (int i = 16; i >= 0; i--)
	{
		if (k & (1 << i))	// 将k看作二进制
		{
			ans = max(ans, down[x][i]);	// 如果点x向上2^i层的祖先节点到节点x能赚取的最大差价更大,则更新ans
			if (max_val > DBL_MIN)
			{
				ans = max(ans, max_val - minVal[x][i]);	// 如果到达当前节点前,买发生在从点x向上2^i层的祖先节点到节点x这条路径上
			}
			max_val = max(max_val, maxVal[x][i]);		// 如果点x向上2^i层的祖先节点到节点x这条路径上的节点最大值更大,则更新max_val
			x = p[x][i];	// x到达向上2^i条边对应的结点
		}
	}
	return ans;
}

// 计算点x向上走k层的路径上能赚取的最大差价,以及顶点的最小权值min_val
double Merchant::QueryUp(int x, int k, double& min_val)
{
	double ans = 0;	// ans表示点x向上走2^k条边的路径上能赚取的最大差价
	min_val = DBL_MAX;
	for (int i = 16; i >= 0; i--)
	{
		if (k & (1 << i))	// 将k看作二进制
		{
			ans = max(ans, up[x][i]);	// 如果点x向上走2^i条边这条路径上能赚取的最大差价更大,则更新ans
			if (min_val < DBL_MAX)
			{
				ans = max(ans, maxVal[x][i] - min_val);	// 如果到达当前节点前,卖发生在从点x向上走2^i条边对应的路径上
			}
			min_val = min(min_val, minVal[x][i]);	// 如果点x向上走2^i条边这条路径上的节点最小值更小,则更新min_val
			x = p[x][i];				// 点x向上走2^i条边
		}
	}
	return ans;
}

void Merchant::Solve()
{
	while (scanf("%d", &n) == 1)
	{
		//AllocMem();
		for (int i = 0; i < n; i++)
		{
			scanf("%lf", &vertex[i].val);
		}
		for (int i = 1; i < n; i++)
		{
			int u = 0, v = 0;
			scanf("%d %d", &u, &v);
			u--;
			v--;
			vertex[u].arcs.push_back(v);
			vertex[v].arcs.push_back(u);
		}
		Init();
		int q = 0;
		scanf("%d", &q);
		for (int i = 0; i < q; i++)
		{
			int u, v;
			scanf("%d %d", &u, &v);
			u--;
			v--;
			int t = LCA(u, v);	// t为u和v的最近公共祖先节点
			double min_val, max_val;
			// t表示点u和点v的最近公共祖先节点,那么从u到v的路径上可以赚取的路径最大值有3种情况:
			// 1.从u到t的up值,即买和卖都发生在节点u到t对应路径上;
			// 2.t到v的maxVal减去从u到t的minVal,即买和卖都发生在节点u到t对应路径上,卖发生在t到节点v对应路径上;
			// 3.t到v的down值,即买和卖都发生在t到节点v对应路径上。
			// 选取一个最大值即为答案。
			double a = QueryUp(u, deep[u] - deep[t], min_val);
			double b = QueryDown(v, deep[v] - deep[t], max_val);
			double ans = max(max(0.0, max_val - min_val), max(a, b));
			printf("%d\n", (int)ans);
		}
		//FreeMem();
	}
}

int main()
{
	Merchant mc;
	mc.Solve();
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator