FlyInTheSky's blog

OI, 梦开始的地方。


  • 首页

  • 关于

  • 标签

  • 分类

  • 归档

  • 朋友

  • 搜索

生成树 学习笔记

发表于 2016-11-27 | 分类于 算法笔记 | | + s

模板及讲解

最小生成树:在一个图中选择$n-1$条边,使所有点连通且路径总权最小。常用算法是用并查集辅助求解的Kruskal
最小瓶颈路:求一条路径,使得$u−>v$路径上的最大边权最小。可以知道,最小瓶颈路必在最小生成树上,所以用最小生成树求解

最小生成树性质

1切割性质
2回路性质
3相同边权数量相等
4不同边权加入时互相独立
5不产生环的同权值边可以替换边

Kruskal 重构树

定义

在做 Kruskal 的时候,我们将边权转点权,得到$2n-1$个点的树。

构造方法

每次 Kruskal 时,如果当前边是需要的,那么我们建立一个新节点,节点权值为边权,然后从这个点向两边两个集合的并查集代表连边。

性质

1、是一棵树,并且是一个二叉堆
2、原最小生成树两点之间的边权最大值是重构树上两点$\text{LCA}$的权值
3、重构树中代表原最小生成树中的点的节点全是叶子节点,其余节点都代表了一条边的边权。

例题

1、Bzoj 3732

给你$N$个点的无向有边权图,图中有$M$条边,现在有$K$个询问,每个询问的格式是:A B,表示询问从$A$点走到$B$点的所有路径中,最长的边最小值是多少?

最长的边最小值,我们考虑最小生成树。这题明显可以求出最小生成树,然后再在树上倍增 / 树剖求出最长的边。这里可以运用性质2,即原最小生成树两点之间的边权最大值是重构树上两点$\text{LCA}$的权值,那么我们构造出重构树,询问树上两点$\text{LCA}$的权值即为答案。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 30000 + 5, LOGS = 20;

    struct edge {
        int u, v, w;
        bool operator < (const edge &rhs) const {return w < rhs.w;}
    } ed[30000 + 5];

    int n, m, Q, val[MAXN], f[MAXN], idx;
    vector<int > G[MAXN];
    int pre[MAXN][LOGS + 2], dep[MAXN];

    void ins(int u, int v) {G[u].push_back(v);}
    int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
    void dfs(int u, int fa) {
        pre[u][0] = fa, dep[u] = dep[fa] + 1;
        for (int i = 1; i <= LOGS; ++i) pre[u][i] = pre[pre[u][i - 1]][i - 1];
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa) dfs(v, u);
        }
    }
    int LCA(int a, int b) {
        if (dep[a] < dep[b]) swap(a, b);
        for (int i = LOGS; i >= 0; --i) if (dep[pre[a][i]] >= dep[b]) a = pre[a][i];
        if (a == b) return a;
        for (int i = LOGS; i >= 0; --i) if (pre[a][i] != pre[b][i]) a = pre[a][i], b = pre[b][i];
        return pre[a][0];
    }

    void clean() {
        ms(val, 0), ms(f, 0);
        ms(pre, 0), ms(dep, 0);
    }
    int solve() {

        clean();
        cin >> n >> m >> Q;
        for (int i = 1; i <= m; ++i) scanf("%d%d%d", &ed[i].u, &ed[i].v, &ed[i].w);
        sort(ed + 1, ed + 1 + m), idx = n;

        // Kruskal
        int tot = 0;
        for (int i = 0; i <= n * 2; ++i) f[i] = i;
        for (int i = 1; i <= m; ++i) {
            int x = find(ed[i].u), y = find(ed[i].v);
            if (x != y) {
                ++idx;
                ins(idx, f[x]), ins(idx, f[y]);
                f[x] = f[y] = idx, val[idx] = ed[i].w;
                ++tot;
                if (tot >= n - 1) break ;
            }
        }

        // LCA
        dfs(idx, 0);

        while (Q--) {
            int x, y; scanf("%d%d", &x, &y);
            printf("%d\n", val[LCA(x, y)]);
        }

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

常见题型

1、求一个图的最小/大生成树
Q:给出一个图,求出这个图的最小/大生成树
解:见讲解
例题:BZOJ 2429
2、将一个图转为树
Q:给出一个图,图中只有使图连通的最大/小的那几条边有用
解:求最小/大生成树。
例题:NOIP2013 D1 T3
3、求一条路径使得最大边最小
Q:给出一个图,求一条路径使得$a->b$最大边最小(这种题的题面一般带有二分的标志:最大值最小)
解:最小瓶颈路。最大边最小的路径在最小生成树上。
例题:BZOJ 2429
4、最小生成树性质
Q:BZOJ 1016
解:BZOJ 1016
例题:BZOJ 1016
5、最小生成树-倍增 (回路性质)
Q:CF 609E
解:CF 609E
例题:CF 609E

阅读全文 »

后缀数组 学习笔记

发表于 2016-11-27 | 分类于 算法笔记 | | + s

模板及讲解

性质

1、字符串中的子串可以表示为后缀的前缀,即后缀的LCP。

模板、代码

解决字符串的有力工具。
直接上代码,注释讲解(此题为uoj #35)
(注意:下标都是从0开始)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "uoj35" 
using namespace std;

const int MAXN = 1000000 + 5;

char ch[MAXN];
int a[MAXN], n, m;
//ch为输入字符串,a为处理后的整数原串 
int SA[MAXN], rk[MAXN], tp[MAXN], tax[MAXN], height[MAXN];
/*
    SA[i]: 排名第i的后缀的位置(下标是后缀排名)
     rk[i]: 第i个后缀的排名
    tp[i]: 排名为i的第二关键字的第一关键字的位置 (下标是第二关键字排名)
    tax[i]:基数排序的桶
    height[i]: 排名为i, i-1后缀的最长公共前缀 
*/
bool cmp(int *f, int i, int k) {return f[SA[i-1]]==f[SA[i]]&&f[SA[i-1]+k]==f[SA[i]+k];} //要判断两个字符串是否完全相等 
void build() {//构造后缀数组 
    int i, p;
    for (int i=0;i<m;i++) tax[i] = 0;
    for (int i=0;i<n;i++) tax[rk[i]=a[i]]++;
    for (int i=0;i<m;i++) tax[i] += tax[i-1];
    for (int i=n-1;i>=0;i--) SA[--tax[rk[i]]] = i;//基数排序排第一轮

    for (int k=1;k<=n;k*=2) {
        p = 0;
        for (int i=n-k;i<n;i++) tp[p++] = i;//(n-k)~(n-1)无第二关键字,所以排序应该排在前面
        for (int i=0;i<n;i++) if (SA[i]>=k) tp[p++] = SA[i] - k;
        //只有SA[i]>=k的SA[i]才是第二关键字的位置 
        //从图中可以看出第一关键字和第二关键字的位置相差k,故SA[i] - k 
        for (int i=0;i<m;i++) tax[i] = 0;
        for (int i=0;i<n;i++) tax[rk[tp[i]]]++;//x[tp[i]]相等于排名第i的第二关键字的第一关键字的排名 
        for (int i=1;i<m;i++) tax[i] += tax[i-1];
        for (int i=n-1;i>=0;i--) SA[--tax[rk[tp[i]]]] = tp[i];//保证了第一关键字的顺序再排第二关键字 
        //基数排序第一关键字(rank[i]的数值)和第二关键字(tp[i]的下标) 
        swap(rk, tp);//此时tp没用,暂存上一轮rank的值
        p = 0, rk[SA[0]] = 0;//sa[0]一定是添加的字符0, 排名一定是0
        for (int i=1;i<n;i++) rk[SA[i]] = cmp(tp, i, k) ? p : ++p;
        //算排名第i的数的rank,按sa顺序能够保证rank的正确性,但是要cmp判断与上一个字符串相等的情况 
        if (++p>=n) break;//剪枝,已经没有重复元素 
        m = p; 
    }
}
void getH() {//算height 
    int i, j, k = 0;//k是比i-1前一名的后缀
    for (int i=0;i<n;i++) {//H[0], H[1], H[2] ...的顺序计算 
        if (k) k--;//从k-1开始比较 ,运用结论H[i]>=H[i-1]-1, 最长公共前缀的长度至少是k-1(k = H[i-1])
        j = SA[rk[i]-1]; //前一名的后缀位置 
        while(ch[i+k] == ch[j+k]) k++; //往后比较 
        height[rk[i]] = k;  //更新答案 
    }
}
void init() {
    int i;
    n = strlen(ch) + 1, m = 128;
    for (int i=0;i<n-1;i++) a[i] = ch[i];//处理原字符串 
    a[n - 1] = 0;//补末尾的0 
}
void solve() {
    int i;
    build(); 
    getH();
    for (int i=1;i<n;i++) printf("%d ", SA[i]+1);//输出范围1~n-1 
    printf("\n");
    for (int i=2;i<n;i++) printf("%d ", height[i]);
}
int main() {
    scanf("%s", ch), init(), solve();
    return 0;
}

从1开始的SA (不用补0):

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "uoj35" 
using namespace std;

const int MAXN = 1000000 + 5;

char ch[MAXN];
int a[MAXN], n, m;
//ch为输入字符串,a为处理后的整数原串 
int SA[MAXN], rk[MAXN], tp[MAXN], tax[MAXN], height[MAXN];
/*
    SA[i]: 排名第i的后缀的位置(下标是后缀排名)
     rk[i]: 第i个后缀的排名
    tp[i]: 排名为i的第二关键字的第一关键字的位置 (下标是第二关键字排名)
    tax[i]:基数排序的桶
    height[i]: 排名为i, i-1后缀的最长公共前缀 
*/
void build() {//构造后缀数组 
    for (int i = 1; i <= m; ++i) tax[i] = 0;
    for (int i = 1; i <= n; ++i) tax[rk[i] = a[i]]++;
    for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
    for (int i = n; i >= 1; --i) SA[tax[rk[i]]--] = i;//基数排序排第一轮

    for (int k = 1; k <= n; k *= 2) {
        int p = 0;
        for (int i = n - k + 1; i <= n; i++) tp[++p] = i;//(n-k)~(n-1)无第二关键字,所以排序应该排在前面
        for (int i = 1; i <= n; i++) if (SA[i] > k) tp[++p] = SA[i] - k;
        //只有SA[i]>=k的SA[i]才是第二关键字的位置 
        //从图中可以看出第一关键字和第二关键字的位置相差k,故SA[i] - k 
        for (int i = 1; i <= m; ++i) tax[i] = 0;
        for (int i = 1; i <= n; ++i) tax[rk[tp[i]]]++;//x[tp[i]]相等于排名第i的第二关键字的第一关键字的排名 
        for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
        for (int i = n; i >= 1; --i) SA[tax[rk[tp[i]]]--] = tp[i];//保证了第一关键字的顺序再排第二关键字 
        //基数排序第一关键字(rank[i]的数值)和第二关键字(tp[i]的下标) 
        swap(rk, tp);//此时tp没用,暂存上一轮rank的值
        p = 1, rk[SA[1]] = 1;
        for (int i = 2; i <= n; ++i) 
            rk[SA[i]] = (tp[SA[i]] == tp[SA[i - 1]] && tp[SA[i] + k] == tp[SA[i - 1] + k]) ? p : ++p;
        //算排名第i的数的rank,按sa顺序能够保证rank的正确性,但是要cmp判断与上一个字符串相等的情况 
        if (p >= n) break;//剪枝,已经没有重复元素 
        m = p; 
    }
}
void getH() {//算height 
    int k = 0;//k是比i-1前一名的后缀
    for (int i = 1; i <= n; ++i) {//H[0], H[1], H[2] ...的顺序计算 
        if (k) k--;//从k-1开始比较 ,运用结论H[i]>=H[i-1]-1, 最长公共前缀的长度至少是k-1(k = H[i-1])
        int j = SA[rk[i] - 1]; //前一名的后缀位置 
        while(ch[i + k] == ch[j + k]) k++; //往后比较 
        height[rk[i]] = k;  //更新答案 
    }
}
void solve() {
    n = strlen(ch + 1), m = 256;
    for (int i = 1; i <= n; ++i) a[i] = ch[i];//处理原字符串 
    build(); 
    getH();
    for (int i = 1; i <= n; ++i) printf("%d ", SA[i]); 
    printf("\n");
    for (int i = 2; i <= n; ++i) printf("%d ", height[i]);
}
int main() {
    scanf("%s", ch + 1), solve();
    return 0;
}

写时注意:
1、不要将字符对应到0
2、不同字符串之间一定要用不同字符连接
3、用不同字符串连接字符串后注意空间开大

阅读全文 »

倍增LCA / DFS序 学习笔记

发表于 2016-11-27 | 分类于 算法笔记 | | + s

模板及讲解

倍增LCA

倍增思想,维护$deep[i], pre[i][j]$为点$i$的深度和点$i$的$2^j$个祖先结点
然后对于每一对$x, y$求$LCA(x, y)$,先把深的结点提上来和浅结点深度相同,如果此时$x, y$都相同,说明$x, y$在同侧,输出$x, y$任意一个即可,否则再一起提上来直到两点相等,输出$pre[x][0]$或者$pre[y][0]$

跳的时候跳二进制,即
设$del = deep[b] - deep[a] (deep[b] >= deep[a])$
如果 $del = 5$, 二进制为$101$
那么从左往右扫描,第$i$位为$1$的就跳$2^i$个点
$del = 5$时,跳$2^2$和$2^0$即可

DFS 序

DFS序的一大重要性质即为连续的一段是一个子树,很多问题可以转化为此。

DFS 序经典问题

给定一棵带点权树根为$1$。
1、单点修改,子树查询 (直接维护)

直接用数据结构维护 DFS 序即可。

2、树链修改,单点查询 (贡献)

考虑将树链分割。若修改$(u,v)+1$则等价于修改$(1,u)+1, (1,v)+1, (1, LCA)-1, (1, fa(LCA)-1)$
那么只用处理根到某个点的树链修改。
修改即修改$dfn(u)+1, dfn(v)+1, dfn(LCA)-1, dfn(fa(LCA))-1$
考虑一个查询一个点$y$,由贡献来看,只有$y$子树的点会对$(1,y)$产生贡献。所以直接查询$y$子树即可。

3、树链修改,子树查询 (贡献)

考虑将树链分割。若修改$(u,v)+1​$则等价于修改$(1,u)+1, (1,v)+1, (1, LCA)-1, (1, fa(LCA)-1)​$
那么只用处理根到某个点的树链修改。
修改即修改$dfn(u)+1, dfn(v)+1, dfn(LCA)-1, dfn(fa(LCA))-1$
考虑一个查询一个子树$y$,由贡献来看,只有$y$子树的点会对$(1,y)$产生贡献。
这里和上面不一样了,设$dep(x)$为$x$深度,$v(x)$为数据结构上$x$的权,则$\forall x \in \operatorname{subtree}(y)$,他的贡献为$(dep(x)-dep(y)) \times v(x)$
转化,得$dep(x) \times v(x) - dep(y) \times v(x)$
写成和的形式,则$\sum\limits_{x \in \operatorname{subtree}(y)} dep(x) \times v(x) - dep(y) \times v(x)$
即$\sum\limits_{x \in \operatorname{subtree}(y)} dep(x) \times v(x) - dep(y) \sum\limits_{x \in \operatorname{subtree}(y)} v(x)$
用数据结构维护$dep(x) \times v(x), v(x)$即可求解。

4、单点修改,树链查询 (差分序列)

考虑将树链分割。若查询$(u,v)$则等价于查询$(1,u)+ (1,v)-(1, LCA)-(1, fa(LCA)-1)$
那么只用处理根到某个点的树链查询。
对于修改$y$,维护差分序列,那就直接差分点$y$的子树即可,答案即为$\sum\limits_{i=1}^{dfn(y)} val(i)$。

5、子树修改,单点查询 (贡献+差分序列 / 直接维护)

对于询问$y$,只有修改$x$是$y$的祖先$x$才会贡献$y$。
所以单点修改$x$,查询$(1,y)$的权和,转化为问题 $4$
或直接用数据结构维护 DFS 序即可。

6、子树修改,子树查询 (直接维护)

直接用数据结构维护 DFS 序即可。

7、子树修改,树链查询 (贡献+差分序列)

和 $4$ 类似的问题。这里就是要处理一下深度,用类似 $2$ 的方法处理即可。
例题:Bzoj 4034

总结:
DFS序的问题主要有几种处理方法:
1、直接维护 (维护原数组)
2、贡献法
3、维护差分序列 (询问前缀和)
本质上还是要将询问变为询问子树(维护原数组),询问前缀和(维护差分序列)

路径交 / 并问题

路径并:Bzoj 3991,Loj 10132(多条路径并)
路径交:CF 832D(两条路径交,并且有一个端点重合),Hdu 6110(多条路径交)

判两条路径有没有交,只要一条链的$lca$在另一条链上就一定有交;取两条路径的交,把两条路径的端点两两求出四对$lca$,最深那两个就是路径交。

阅读全文 »

线段树 学习笔记

发表于 2016-11-27 | 分类于 算法笔记 | | + s

模板及讲解

什么时候要用线段树?
1、统计量可合并
2、修改量可合并
3、通过修改量可直接修改统计量
⼀句话: 满⾜区间加法即可使用线段树维护信息

常见题型

1、线段树合并区间
在区间维护若干个值。
例题:BZOJ 1593
2、离散化
解:运用二分查找进行离散化。1、全部顶点加入数组 2、排序去重 3、值相差大于1的中间插一个值(直接在末尾插$val[i-1]+1$, 再作sort即可)
例题:Hdu 1542

阅读全文 »

差分约束 学习笔记

发表于 2016-11-27 | 分类于 算法笔记 | | + s

模板及讲解

差分约束是什么

差分约束就是给出一些形如$x-y \ge c$的约束,问你是否有解,或求最大、最小解。该问题可以转化为图上最短路问题。

差分约束的几种形式

求最大差

建立形如 $A-B \le C$ 的不等式,在原图中添加边 $B->A$ 边权为 $C$
对建好的图跑最短路,如果存在负环,无解(判断条件为某点被更新了$ n $次),$n $为图中点的数量

求最小差

建立形如 $A-B \ge C$ 的不等式,在原图中添加边 $B->A$ 边权为 $C$
对建好的图跑最长路,如果存在正环,无解(判断条件为某点被更新了$ n$ 次),$n$ 为图中点的数量

我们可以建立一个虚结点,然后让这个虚结点指向所有图中的结点,权值为0,从虚结点开始求最短路。(还可以先把所有点加入队列,之后dis全部初始化为0)

不等式标准化方法

如果有一个不等式为$x-y>c$, 则可变为$x-y \ge c+1$
同理$x-y<c$可变为$x-y \le c-1$
如果是$x-y=c$,则变为两个式子$x-y\le c, x-y \ge c$

阅读全文 »

Hdu 1561(树形背包DP)

发表于 2016-09-14 | 分类于 Hdu | | + s

Hdu 1561
经典树形依赖背包问题。
因为可能出现森林,所有要建立一个虚结点0,将森林中所有树的根节点作为结点0的儿子
$f[i][j]$表示以i为根选j个课程
$f[u][j] = max(f[u][j], f[u][j-k]+f[v][k])$ v是u的儿子

阅读全文 »
1…5859
FlyInTheSky

FlyInTheSky

自己选择的路,跪着也要走完。

586 日志
19 分类
144 标签
一言
© 2016 — 2019 FlyInTheSky
由 Hexo 强力驱动
|
主题 — NexT.Gemini v6.0.3
Hosted by Coding Pages
本站总访问量次