POJ 1330(Nearest Common Ancestors-Lca模板题)

Nearest Common Ancestors
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 13559   Accepted: 7236

Description

A rooted tree is a well-known data structure in computer science and engineering. An example is shown below: 

 
In the figure, each node is labeled with an integer from {1, 2,...,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor
of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node
x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common
ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is. 

For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest
common ancestor of y and z is y. 

Write a program that finds the nearest common ancestor of two distinct nodes in a tree. 

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case starts with a line containing an integer N , the number of nodes in a tree, 2<=N<=10,000. The nodes are labeled with integers 1, 2,...,
N. Each of the next N -1 lines contains a pair of integers that represent an edge --the first integer is the parent node of the second integer. Note that a tree with N nodes has exactly N - 1 edges. The last line of each test case contains two distinct integers
whose nearest common ancestor is to be computed.

Output

Print exactly one line for each test case. The line should contain the integer that is the nearest common ancestor.

Sample Input

2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5

Sample Output

4
3

Source


Rt,纯粹无聊写的……(其实至今为止就写过2个………("▔□▔)/)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (10000+10)
#define Li (17)
int t,n,father[MAXN][Li];
int edge[MAXN],pre[MAXN],next[MAXN],size=0;
void addedge(int u,int v)
{
	edge[++size]=v;
	next[size]=pre[u];
	pre[u]=size;
}

int queue[MAXN],deep[MAXN],bin[Li];
void bfs()
{
	int head=1,tail=1;
	for (int i=1;i<=n;i++)
		if (!father[i][0]) {queue[1]=i;deep[i]=1;break;}
	while (head<=tail)
	{
		int &u=queue[head];
		for (int i=1;i<Li;i++)
		{
			father[u][i]=father[father[u][i-1]][i-1];
			if (father[u][i]==0) break;
		}
		for (int p=pre[u];p;p=next[p])
		{
			int &v=edge[p];
			deep[v]=deep[u]+1;
			queue[++tail]=v;
		}
		head++;
	}
}
int lca(int x,int y)
{
	if (x==y) return x;
	if (deep[x]<deep[y]) swap(x,y);
	int t=deep[x]-deep[y];
	for (int i=0;i<Li;i++)
		if (bin[i]&t)
		{
			x=father[x][i];
		}
	int i=Li-1;
	while (x^y)
	{
		while (father[x][i]==father[y][i]&&i) i--;
		x=father[x][i];y=father[y][i];
	}
	return x;
}
int main()
{
//	freopen("poj1330.in","r",stdin);
	scanf("%d",&t);
	for (int i=0;i<Li;i++) bin[i]=1<<i;

	while (scanf("%d",&n)!=EOF)
	{
		memset(pre,0,sizeof(pre));size=0;
		memset(father,0,sizeof(father));
		for (int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			father[v][0]=u;
			addedge(u,v);
		}
		bfs();
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%dn",lca(x,y));

	}
	return 0;
}

BZOJ 1977([BeiJing2010组队]次小生成树 Tree-LCA的位运算)

1977: [BeiJing2010组队]次小生成树 Tree

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1176  Solved: 234
[Submit][Status][Discuss]

Description

小 C 最近学了很多最小生成树的算法,Prim 算法、Kurskal 算法、消圈算法 等等。 正当小 C 洋洋得意之时,小 P 又来泼小 C 冷水了。小 P 说,让小 C 求出一 个无向图的次小生成树,而且这个次小生成树还得是严格次小的,也就是说: 如果最小生成树选择的边集是 EM,严格次小生成树选择的边集是 ES,那么 需要满足:(value(e) 表示边 e的权值) 这下小
C 蒙了,他找到了你,希望你帮他解决这个问题。

Input

第一行包含两个整数N 和M,表示无向图的点数与边数。 接下来 M行,每行 3个数x y z 表示,点 x 和点y之间有一条边,边的权值 为z。

Output

包含一行,仅一个数,表示严格次小生成树的边权和。(数 据保证必定存在严格次小生成树)

Sample Input

5 6

1 2 1

1 3 2

2 4 3

3 5 4

3 4 3

4 5 6

Sample Output

11

HINT

数据中无向图无自环; 
50% 的数据N≤2 000 M≤3 000; 
80% 的数据N≤50 000 M≤100 000; 
100% 的数据N≤100 000 M≤300 000 ,边权值非负且不超过 10^9

Source

这题的关键就在于求Lca,记录路径上的最小与严格次小值.

用f[i][j]表示i的第2^j个儿子(0 表示 不存在)

那么f[i][j]=f[ f[i][ j-1] ][j-1]

dp[i][j]和dp0[i][j]表示点i到f[i][j]的最小和严格次小值(不存在=-1),那么只需特判即可.

int lca(int x,int y,int &nowdp,int &nowdp0)
{
	if (deep[x]<deep[y]) swap(x,y);
	int t=deep[x]-deep[y]; //差的数量
	for (int i=0;t;i++)
		if (t&bin[i])   //转化为位运算 bin[i]表示2<<i 把t看成2进制
		{
			x=f[x][i];
			t-=bin[i];
		}
	int i=Li-1; //Li 表示 最高存到2^(Li-1)个父亲
	while (x^y) //x和y不相等时
	{
		while (f[x][i]==f[y][i]&&i) i--; //当i==0时只能向上跳
		x=f[x][i];y=f[y][i];
	}
}

程序:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (100000+10)
#define MAXM (600000+10)
#define Li (17)
#define INF (2000000000)
int edge[MAXM],pre[MAXM],weight[MAXM],next[MAXM],size=0;
int addedge(int u,int v,int w)
{
	edge[++size]=v;
	weight[size]=w;
	next[size]=pre[u];
	pre[u]=size;
}
int addedge2(int u,int v,int w)
{
	addedge(u,v,w);
	addedge(v,u,w);
}
int f[MAXN][Li]={0},dp[MAXN][Li]={0},dp0[MAXN][Li]={0},deep[MAXN],n,m;
struct E
{
	int u,v,w;
	friend bool operator<(E a,E b){return a.w<b.w;	}
}e[MAXM];
bool b[MAXM],vis[MAXN];
int queue[MAXN],head,tail;
void bfs()
{
	memset(vis,0,sizeof(vis));
	head=tail=1;queue[1]=1;vis[1]=1;deep[1]=0;
	while (head<=tail)
	{
		int &u=queue[head];
		if (u!=1)
		{
			for (int i=1;i<17;i++)
			{
				if (f[u][i-1])
				{
					f[u][i]=f[f[u][i-1]][i-1];
				}
				if (f[u][i]==0) break;
				if (f[u][i])
				{
					dp[u][i]=max(dp[u][i-1],dp[f[u][i-1]][i-1]);
				}
				if (i==1)
				{
					if (dp[u][0]!=dp[f[u][0]][0]) dp0[u][1]=min(dp[u][0],dp[f[u][0]][0]);
					else dp0[u][1]=-1;
				}
				else
				{
					dp0[u][i]=max(dp0[u][i-1],dp0[f[u][i-1]][i-1]);
					if (dp[u][i-1]!=dp[f[u][i-1]][i-1]) dp0[u][i]=max(dp0[u][i],min(dp[u][i-1],dp[f[u][i-1]][i-1]));
				}
			}
		}
		for (int p=pre[u];p;p=next[p])
		{
			int &v=edge[p];
			if (!vis[v])
			{
				queue[++tail]=v;
				vis[v]=1;deep[v]=deep[u]+1;
				f[v][0]=u;dp[v][0]=weight[p];dp0[v][0]=-1;
			}
		}
		head++;
	}
}
int bin[Li];
void check(int &nowdp,int &nowdp0,int c)
{
	if (c<=nowdp0) return;
	else if (nowdp0<c&&c<nowdp) nowdp0=c;
	else  if (c==nowdp) return;
	else if (nowdp<c) {nowdp0=nowdp;nowdp=c;}
}
int lca(int x,int y,int &nowdp,int &nowdp0)
{
	nowdp=nowdp0=-1;
	if (deep[x]<deep[y]) swap(x,y);
	int t=deep[x]-deep[y];
	for (int i=0;t;i++)
		if (t&bin[i])
		{
			check(nowdp,nowdp0,dp[x][i]);
			check(nowdp,nowdp0,dp0[x][i]);
			x=f[x][i];
			t-=bin[i];
		}
	int i=Li-1;
	while (x^y)
	{
		while (f[x][i]==f[y][i]&&i) i--;
		check(nowdp,nowdp0,dp[x][i]);
		check(nowdp,nowdp0,dp0[x][i]);
		check(nowdp,nowdp0,dp[y][i]);
		check(nowdp,nowdp0,dp0[y][i]);
		x=f[x][i];y=f[y][i];
	}
}
int father[MAXN];
long long sum_edge=0;
int getfather(int x)
{
	if (father[x]==x) return x;
	father[x]=getfather(father[x]);
	return father[x];
}
void union2(int x,int y)
{
	father[father[x]]=father[father[y]];
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) father[i]=i;
	memset(b,0,sizeof(b));
	memset(next,0,sizeof(next));
	for (int i=0;i<Li;i++) bin[i]=1<<i;
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	}
	sort(e+1,e+1+m);
	for (int i=1;i<=m;i++)
	{
		if (getfather(e[i].u)!=getfather(e[i].v)) {union2(e[i].u,e[i].v);addedge2(e[i].u,e[i].v,e[i].w);sum_edge+=e[i].w;	}
		else b[i]=1;
	}
	bfs();

	long long mindec=-1;
	for (int i=1;i<=m;i++)
		if (b[i])
		{
			int nowdp,nowdp0;
			lca(e[i].u,e[i].v,nowdp,nowdp0);
			if (nowdp==e[i].w) nowdp=nowdp0;
			if (nowdp==-1) continue;
			if (mindec==-1||mindec>e[i].w-nowdp) mindec=e[i].w-nowdp;
		}
	printf("%lldn",sum_edge+mindec);
	return 0;
}