Poj 3728 The merchant (tarjan-LCA高级应用)

男娘i 2022-08-24 14:18 12阅读 0赞

题意：给出n个点买入与卖出商品的价格，然后给出n-1条边。 问： 从u-v上进行一次交易的最大获益：可以选一个在u-v之间的点买入，然后再这个点之后的点卖出。

参考了：http://blog.csdn.net/waitfor\_/article/details/7264132

思路：tarjan离线LCA，离线可以计算出查询的一个点到祖先的最优值，然后记录结果，等整个该祖先的子树都遍历完，就可以知道祖先到达查询的另一点的最优值，两者合并就是查询结果，注意考虑方向。

#include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    #define max(a,b) ((a)>(b)?(a):(b))
    #define max3(a,b,c) (max(a,max(b,c)))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int N=50005;
    
    int data[N],thead[N],qhead[N],head[N];  //treehead,quehead
    int e=0,n,m,father[N],ans[N];
    int mi[N],mx[N];  //一路最小价格,最大价格
    int up[N],down[N]; //上下行最大利润
    bool vis[N];
    
    struct Node
    {
    	int v,next;
    	int from,id;
    }edge[N*4];
    
    int find (int u)
    {//更新数据
    	if (father[u]==u) return u;
    	int tmp=father[u];
    	father[u]=find(father[u]);
    	up[u]=max3(up[u],up[tmp],mx[tmp]-mi[u]);
    	down[u]=max3(down[u],down[tmp],mx[u]-mi[tmp]);
    	mx[u]=max(mx[u],mx[tmp]);
    	mi[u]=min(mi[u],mi[tmp]);
    	return father[u];
    }
    
    void tarjan (int u)
    {
    	int i,j;
    	father[u]=u;  //初始化父节点为自身
    	for (i=thead[u];i!=-1;i=edge[i].next)
    	{
    		int v=edge[i].v;
    		if (vis[v]==false)
    		{
    			tarjan(v);
    			father[v]=u;
    		}
    	}
    	vis[u]=true;
    	for (i=qhead[u];i!=-1;i=edge[i].next)
    	{
    		int v=edge[i].v;
    		if (vis[v])
    		{//直接连接祖先与孩子的邻接表
    			int t=find(v);
    			edge[e].id=i;
    			edge[e].next=head[t],head[t]=e++;
    		}
    	}    //根据u,v的方向合并
    	for (i=head[u];i!=-1;i=edge[i].next)
    	{
    		int tmp=edge[i].id;
    		int t=edge[tmp].id,x=edge[tmp].from,y=edge[tmp].v;
    		find(x);
    		if (t<0)
    		{
    			swap(x,y);
    			t=-t;
    		}
    		ans[t]=max3(up[x],down[y],mx[y]-mi[x]);
    	}
    }
    
    void Input ()
    {
    	int i,u,v;
    	for (i=1;i<=n;i++)
    	{
    		scanf("%d",&data[i]);
    		mi[i]=mx[i]=data[i];
    	}
    	memset(up,0,sizeof(up));
    	memset(down,0,sizeof(down));
    	memset(thead,-1,sizeof(thead));
    	memset(qhead,-1,sizeof(qhead));
    	memset(head,-1,sizeof(head));
    	memset(vis,false,sizeof(vis));
    	for (i=1;i<n;i++)
    	{
    		scanf("%d%d",&u,&v);
    		edge[e].v=v;
    		edge[e].next=thead[u],thead[u]=e++;
    	}
    	scanf ("%d",&m);
    	for (i=1;i<=m;i++)
    	{
    		scanf("%d%d",&u,&v);
    		edge[e].v=v;
    		edge[e].from=u,edge[e].id=i,edge[e].next=qhead[u],qhead[u]=e++;
    		edge[e].v=u;
    		edge[e].from=v,edge[e].id=-i,edge[e].next=qhead[v],qhead[v]=e++; //注意反向边标记为-i
    	}
    }
    
    int main ()
    {
    	scanf("%d",&n);
    	Input ();
    	tarjan(1);
    	for (int i=1;i<=m;i++)
    		printf("%d\n",ans[i]);
    	return 0;
    }

补一组测试数据，摘自 http://waihonhon.blogspot.com/2010/01/pku-3728-merchant.html

INPUT :

9
    4 3 1 7 6 9 8 2 5
    1 2
    2 4
    2 5
    1 3
    3 6
    3 7
    3 8
    7 9
    81
    1 1
    1 2
    1 3
    1 4
    1 5
    1 6
    1 7
    1 8
    1 9
    2 1
    2 2
    2 3
    2 4
    2 5
    2 6
    2 7
    2 8
    2 9
    3 1
    3 2
    3 3
    3 4
    3 5
    3 6
    3 7
    3 8
    3 9
    4 1
    4 2
    4 3
    4 4
    4 5
    4 6
    4 7
    4 8
    4 9
    5 1
    5 2
    5 3
    5 4
    5 5
    5 6
    5 7
    5 8
    5 9
    6 1
    6 2
    6 3
    6 4
    6 5
    6 6
    6 7
    6 8
    6 9
    7 1
    7 2
    7 3
    7 4
    7 5
    7 6
    7 7
    7 8
    7 9
    8 1
    8 2
    8 3
    8 4
    8 5
    8 6
    8 7
    8 8
    8 9
    9 1
    9 2
    9 3
    9 4
    9 5
    9 6
    9 7
    9 8
    9 9

OUTPUT:

0
    0
    0
    4
    3
    8
    7
    1
    7
    1
    0
    1
    4
    3
    8
    7
    1
    7
    3
    3
    0
    6
    5
    8
    7
    1
    7
    1
    0
    1
    0
    3
    8
    7
    1
    7
    1
    0
    1
    4
    0
    8
    7
    1
    7
    3
    3
    0
    6
    5
    0
    7
    1
    7
    3
    3
    0
    6
    5
    8
    0
    1
    0
    3
    3
    0
    6
    5
    8
    7
    0
    7
    3
    3
    3
    6
    5
    8
    3
    3
    0