Kruskal 重构树入门 – 「NOI 2018」 归程

Kruskal 重构树

Kruskal 最小/大生成树 — Luogu P1967 货车运输 一文中,介绍了 Kruskal 算法是如何生成最小生成树的

如果将两个联通块联通的不是边而是点呢?

这就是 Kruskal 重构树

具体来说就是,我们原来是通过一条边将两个联通块相连接的,现在我们新建立一个点,将这两个联通块的根节点连接到这个点上,原来的边权就是这个新建节点的点权,这样执行下来,我们会得到一棵新的树,这个树有以下两个特征

  • 没有 边权
  • 保证是一个堆
    • 大根堆还是小根堆要看 原来 生成的是最小还是最大生成树
    • 因为我们保证边权的单调性,故后期新建节点的点权也是单调的,故新树是一个堆
继续阅读“Kruskal 重构树入门 – 「NOI 2018」 归程”

Kruskal 最小/大生成树 — Luogu P1967 货车运输

1 最小生成树

1.1 生成树

无向图 $G$ 的生成树,就是具有图 $G$ 的所有顶点,但是边数最小的联通子图

更加详细的定义: Wikipedia – 生成树

1.2 最小生成树

带权联通无向图的总权值最小的生成树

更加详细的定义: Wikipedia – 最小生成树

1.3 求解算法

  • Kruskal 算法
  • Prim 算法
继续阅读“Kruskal 最小/大生成树 — Luogu P1967 货车运输”

Luogu P2624 [HNOI2008]明明的烦恼

题目链接: https://www.luogu.org/problemnew/show/P2624

0 前置技能

1 推式子时间

这个题目很像 Luogu P2290

但是问题在于,这个里面具有不确定的度数

经过简单的思考,我们可以得出以下式子
$$
C_{n – 2}^{cnt} \times \frac{sum!}{\prod_{i = 1}^{cnt} (d_i – 1)!} \times (n – cnt) ^{n – sum – 2}
$$
其中

  • $sum$ 为已知总度数
  • $cnt$ 为已知点数
继续阅读“Luogu P2624 [HNOI2008]明明的烦恼”

Prufer序列 入门 — P2290 [HNOI2004]树的计数

0 前置知识点

1 Prufer 序列

对于一个带编号的无根树,其 Prufer 序列按以下过程处理

  1. 选取所有节点中度数最小编号最小的一个节点
  2. 输出其相邻的编号
  3. 回到 1 ,直到只剩两个节点为止

每个 Prufer 序列,都对应唯一的一个带编号的无根树

继续阅读“Prufer序列 入门 — P2290 [HNOI2004]树的计数”

Luogu P2607 [ZJOI2008]骑士

题目链接: https://www.luogu.org/problemnew/show/P2607

题目意思非常简单,给你一张图,然后图中不能选最大相邻点,最后最大的选中的点的权值

很容易想到 没有上司的舞会 这种树形 DP 题目,但是显然,这,并不是一棵树

根据题目可得,每一个人只会有一条出边,即,这张图中,一张节点个数为 $n$ 的联通块,会有 $n$ 条边

环套树没得跑了

即每一个联通块中一定有一条边,删掉后就是树了

设这条边为 $u – v$ 的边,则 $\max(f_{u,0}, f_{u,1})$ 就是这个联通块的答案

建双向边判环即可

至于代码中的 xor ,当反向边即可

继续阅读“Luogu P2607 [ZJOI2008]骑士”

Luopu P1525 关押罪犯 —— 初学二分图

二分图

二分图是什么?可以吃吗
可以吃而且很好吃 当然不可以吃,但是使用起来可是个好东西 对于一张无向图,如果他的所有的点可以分成两个点集,且每个点集内的点没有边相连,我们就称这张图为二分图 对于判定二分图,我们有一种非常简单的方法 —— 染色法

染色法


染色?染什么色?
实际上如果有精通小学奥数的同学应该知道,我们在解决一类问题的时候,就会用到染色法来分类,当然,今天的原理,和那个染色法有一点类似 根据二分图的定义每个点集内的点没有边相连,我们可以知道,和一个点相连的两条边一定不在同一个集合中,那么如何判断是不是在同一集合呢? 我们就可以吧同一类的染上一个颜色,然后遍历图,如果我们在遍历某个点的时候,发现下一个点已经遍历过了,且和当前点颜色一样,那么这一定不是二分图 代码如下:
inline bool bfs(int u){// u 起始点
    head=tail=0;// 队列初始化
    col[u]=1;// 初始化起点
    q[head]=u;// 加入对头
    while(head<=tail){// 标准不解释
        int top=q[head];// 去头部
        for(int i=ehead[top];i;i=e[i].next){// 标准遍历不解释
            int to=e[i].to;
            if(col[to]==0){// 如果没有被访问过
                col[to]=3-col[top];// 染色
                q[++tail]=to;// 加入队列
            }
            else {// 访问过
                if(col[to]==col[top]) return false;// 颜色相同当然不是二分图了
            }
        }
        head++;
    }
    return true;
}
但是有的时候,输入数据不保证为一张图,这个时候就要遍历点,如果当前点没有访问过,那么就从当前点起始染色

Luopu P1525 关押罪犯

二分查找二分图 题目链接: [https://www.luogu.org/problemnew/show/P1525]
第一眼看过去,这是什么?可和二分图有啥关系 然后看了看书,突然就明白了 我们可以二分事件的最大影响值,把每个罪犯看做一个点,如果影响值大于mid那么就链接,否则当不存在这条边 所以这道题目就是一个二分模板+染色判二分图

程序


#include <cstdio>
#include <cstring>
using namespace std;
int n,m;
int u,w,v;
int l,r,mid,max;
// edge start
struct edge{
    int to,next,val;
}e[210000];
int ehead[21000],ecnt;
inline void add(int now,int to,int val){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].val=val;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
// edge end
// edge 链表建图部分
// queue start
int q[110000],head,tail;
int col[110000];
inline bool bfs(int u){
    head=tail=0;
    col[u]=1;
    q[head]=u;
    while(head<=tail){
        int top=q[head];
        for(int i=ehead[top];i;i=e[i].next){
            int to=e[i].to;
            if(e[i].val>=mid){// 大于等于mid时建边
                if(col[to]==0){
                    col[to]=3-col[top];
                    q[++tail]=to;
                }
                else {
                    if(col[to]==col[top]) return false;
                }
            }
        }
        head++;
    }
    return true;
}
// queue end
// queue 染色法判图
inline bool rs(){
    for(int i=1;i<=n;i++){
        if(col[i]==0)
            if(!bfs(i)) return false;
    }
    return true;
}
// rs 遍历点
inline void init(){
    memset(col,0,sizeof(col));
}
// init 预处理
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        max=max>w?max:w;// 保留最大用于二分上限
        add(u,v,w);
        add(v,u,w);
    }
    l=0,r=max+1;// 标准二分
    while(l+1<r){
        init();
        mid=(l+r)>>1;
        if(rs()) r=mid;// 如果可以达成[二分图成立] 则缩小范围
        else l=mid;// 不可以就扩大范围
    }
    printf("%d",l);
}
请勿抄袭

END

]]>