LCA

POJ 3728 The merchant

Posted on

LCA 好题!

这道题我暂时只知道用Tarjan的解法。
Tarjan解法完美地运用了Tarjan的核心原理与性质:
深度优先搜索时的向下局部性。自己乱取得,蛤蛤蛤

题意:
给你一棵树,每个节点有一个权值。给你很多个询问,每个询问两个点。要你在给定点的树链上找到有序的最大差值。

思路:
首先考虑分治。设树链 u -> lca -> v
答案无非只有三种情况:

  1. u -> lca 的最大差值
  2. lca -> v 的最大差值
  3. lca -> v 的最大值 - u -> lca 的最小值

考虑dp维护这四个值。
因为运用Tarjan算法的时候,基于dfs,在你的眼里,当前节点就是向下整棵树的根节点,你完全不会去考虑往上的节点。
所以你现在使用的四个值,刚好是你当前节点的孩子节点的最优值。
基于这个事实,我们可以对其状态转移并维护。

AC Code

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;

int n;
int val[maxn], res[maxn];
int up[maxn], down[maxn], max_val[maxn], min_val[maxn];
int root[maxn];
bool vis[maxn];

vector<int> g[maxn];
vector<pii> q[maxn];
vector<pii> ans[maxn];

int findRoot(int x)
{
    if (root[x] == x)
        return x;
    int fa = root[x];
    root[x] = findRoot(root[x]);
    up[x] = max(up[x], max(up[fa], max_val[fa] - min_val[x]));
    down[x] = max(down[x], max(down[fa], max_val[x] - min_val[fa]));
    max_val[x] = max(max_val[x], max_val[fa]);
    min_val[x] = min(min_val[x], min_val[fa]);
    return root[x];
}

void tarjan(int u)
{
    root[u] = u;
    vis[u] = true;
    int sz = q[u].size();
    for (int i = 0; i < sz; i++) {
        int v = q[u][i].second;
        if (vis[v]) {
            int lca = findRoot(v);
            ans[lca].push_back(make_pair(u, i));
        }
    }
    sz = g[u].size();
    for (int i = 0; i < sz; i++) {
        int v = g[u][i];
        if (!vis[v]) {
            tarjan(v);
            root[v] = u;
        }
    }
    sz = ans[u].size();
    for (int i = 0; i < sz; i++) {
        int x = ans[u][i].first, y = q[x][ans[u][i].second].second;
        int id = q[x][ans[u][i].second].first;
        if (id < 0) {
            id = -id;
            swap(x, y);
        }
        findRoot(x), findRoot(y);
        res[id] = max(up[y], down[x]);
        res[id] = max(res[id], max_val[x] - min_val[y]);
    }
}

void init()
{
    for (int i = 0; i <= n; i++) {
        g[i].clear(), q[i].clear(), ans[i].clear();
        vis[i] = false;
        up[i] = down[i] = 0;
    }
}

int main()
{
    int u, v, qnum;
    while (scanf("%d", &n) != EOF) {
        init();
        for (int i = 1; i <= n; i++) {
            scanf("%d", val + i);
            min_val[i] = max_val[i] = val[i];
        }
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        scanf("%d", &qnum);
        for (int i = 1; i <= qnum; i++) {
            scanf("%d %d", &u, &v);
            q[u].push_back(make_pair(-i, v));
            q[v].push_back(make_pair(i, u));
        }
        tarjan(1);
        for (int i = 1; i <= qnum; i++)
            printf("%d\n", res[i]);
    }
    return 0;
}
带权并查集

HDU 2818 && POJ1988 Cube Stacking

Posted on

今天打比赛前写的一道带权并查集

题意 搬砖头 把包含有 a的砖头堆里的 所有砖头 转移到 包含b的砖头堆上 问 K砖头下有几块砖头

思路 :并查集 额外开两个数组 一个记录这堆砖头堆的砖头高度 另一个记录k砖头下有几块砖头 每次合并的时候更新砖头高度 和被合并的砖头堆 最底下砖头 下面有几块砖头 用户find 时更新

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#include <cstdlib>

using namespace std;
const int maxn=30005;
int root[maxn],under[maxn],height[maxn];
void init(int n)
{
    for(int i=0;i<=n;i++)
        root[i]=i,under[i]=0,height[i]=1;
}

int fin(int x)
{
    if(root[x]==x) return x;
    int rot=root[x];
    root[x]=fin(root[x]);
    under[x]+=under[rot];//递归更新要查找的点
    return root[x];
}

void Union(int u,int v)
{
    int ru=fin(u);
    int rv=fin(v);
    if(ru==rv) return;
    root[ru]=rv;//ru堆的最底下变成了rv
    under[ru]=height[rv];//ru砖头下有rv块砖头
    height[rv]+=height[ru];//更新rv堆砖头高度
}

int main()
{
    char ch[5];
    int u,v,n;
    while(scanf("%d",&n)!=EOF)
    {
        init(n<30000?n:30000);
        for(int i=0;i<n;i++)
        {
            scanf("%s",ch);
            if(ch[0]=='M')
            {
                scanf("%d%d",&u,&v);
                Union(u,v);
            }
            else
            {
                scanf("%d",&u);
                fin(u);//这里必须有   因为算法是延迟更新的    这里如果不查找   就不会更新
                printf("%d\n",under[u]);
            }
        }
    }
    return 0;
}
带权并查集

HDU3047 Zjnu Stadium

Posted on

最近一周好好把并查集和最短路走的尽量远一点 再然后就得往RMQ 差分约束 网络流方向走了

扯回来扯回来 刚写的一道带权并查集问题 (因为其实我的并查集基础很薄

并且再之前已经好几次碰到类似的问题了 就是说 带权并查集再合并两棵树的时候 他们各个节点是如何处理的 一直以来我都想不到好方法 今天刚写完这题 我才算明白算法的强大与互通性 看完其他人的博客 我马上意识到 —— 是在线段树里的 延迟更新 也就是说我先做个标记 当我访问的时候 我需要的时候再更新

而这里也是一个道理 我只对被合并的树 的根节点进行更新 当要访问这棵树的叶子节点 我再对其逐个节点递归更新 一直到访问节点

这个思路的博客其实是有很多的 但我实在是忍不住发一个 毕竟对我来说又是一大冲击

AC Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <algorithm>

using namespace std;
const int maxn=50005;
int root[maxn],value[maxn];
int n,m;

void init()
{
    for(int i=0;i<=n;i++)
        root[i]=i,value[i]=0;
}

int fin(int x)
{
    if(root[x]==x) return x;
    int kao=root[x];
    root[x]=fin(root[x]);
    value[x]+=value[kao];//厉害
    return root[x];
}

bool Union(int a,int b,int x)
{
    int ra=fin(a);
    int rb=fin(b);
    if(ra==rb)
    {
        if(value[a]+x!=value[b]) return false;
        return true;
    }
    root[rb]=ra;
    value[rb]=value[a]+x-value[b];
    return true;
}

int main()
{
    int a,b,x;
    while(~scanf("%d%d",&n,&m))
    {
        init();
        int cnt=0;
        while(m--)
        {
            scanf("%d %d %d",&a,&b,&x);
            if(!Union(a,b,x))
                cnt++;
        }
        printf("%d\n",cnt);
    }
    return 0;
}