寒假集训总结

最小生成树

1. Prim

   把点分为已经加入 $MST$ 的 和未被加入的，每次把距离已加入的点最近的边加入 $MST$ 中。

2. Kruskal

   把边从小到大排序，不会产生环就加入，否则跳过。

   证明:

   考虑归纳法。

   若当前只存在 最小边链接的节点，则答案为最小边。

   若当前只存在 最小边链接的节点，则答案为最小边。

   设当前 边集为 $E$，点集为 $V$，当前处理的边为 $u \rightarrow v$。

   • 若 $u,v \in V$ ，则 加入 会存在环，你需要替换环上的一条边。

     但 环上的边的权值 均不大于 当前边的权值，所以当前的 $MST$ 不会更劣。

   • 否则，加入。

   由 $Kruskal$ 引出的一些问题：

   1. 重构树

      用于求解 两点之间的 最大路最小/最小路最大。

      在求最小生成树中，我们把 加边的两个节点挂在一个虚拟节点下方，并把根设为这个虚拟节点。

      void Kruskal()
      {
          sort(...);
          for(i: E)
          {
              int A=find(e[i].from),B=find(e[i].to);
              if(A!=B)
              {
                  tot++;//tot是虚拟节点编号。
                  fa[tot]=tot,w[tot]=e[i].w;//w[]为点权
                  merge(A,tot),merge(B,tot);
                  cost+=e[i].w;
              }
          }
      }

      此时 两点的LCA 就是答案。

   2. 判断一条边是否 一定/可能/不会 存在于 $MST$ 上。

      将边按照边权分类。

      每一次加入 所有边权相等的边。

      • 若存在环，则环上的边是 可能存在。
      • 桥 是一定存在。

      对于环，用并查集缩一下，把连通块看作点( 树上加边一定会形成环，转为自环 )。

---

拓扑排序

• 字典序最小

  把 $queue$ 变成 $queue$。

  要注意区别 字典序最大在倒过来(菜肴制作)。

• 差分约束

  形如 $x_i - x_j \le c_i$。

  由三角不等式 $dist_{i,j}+dist_{j,k} ≥ dist_{i,k}$ ，上式等价于

  $~~~~~~~~~~~~~~~~~~~~~~~~ x_i+c≥x_j$。

  从 $x_i$ 向 $x_j$ 连边即可。

  如果是 $\frac{x_i}{x_j} ≥ c$ ，两边同取对数得：$log_{x_i}-log_{x_j}≥c$。

---

二分图

1. 判断

   染色法。

   本质是没有奇环。

2. 最大匹配

   int dfs(int u)
   {
       for(int i:g[u])
       {
           if(i未被访问)
           {
           	   vis[i]=true;
               if(!book[i] || dfs(book[i]))
               {
                   book[i]=u;
                   return true;
               }
           }
       }
       return false;
   }

---

欧拉路

• 判定

  1. 无向

     

     环上和链上的入度 %2==0。

     所以

     ​ 存在欧拉路: 两个点的度为奇，其他为偶

     ​ 存在欧拉回路：度全为偶

  2. 有向

     存在欧拉回路：每个顶点的入度和出度相等

• Hierholzer

  void Hierholzer(int u)
  {
      for(int i:g[u])
      {
          删边 ( i->u);
          Hierholzer(i);
      }
      cout<<u<<"　"；
  }

---

并查集

需要撤销时可以考虑

1. 倒加边
2. 一次回退一步
3. 可持久化并查集

---

线段树

代码力。

注意 lazy 的顺序。

奇技淫巧:

「学习笔记」线段树标记永久化

zkw 线段树

算法学习笔记(76): zhw线段树

算法学习——zhw线段树

zhw线段树 模板整理与例题

P3369 【模板】普通平衡树

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e6+3;
int n,m;
struct node{
    int opt,data;
}q[N];
vector<int> pos;

struct Tree{
    int idx=2;
    struct node{
        #define ls a[u].l_idx
        #define rs a[u].r_idx
        #define mid ((a[u].l+a[u].r)>>1)
        int l,r,l_idx,r_idx;
        int data;
    }a[N];

    void push_up(int u)
    {
        a[u].data=a[ls].data+a[rs].data;
    }
    void build(int u,int l,int r)
    {
        a[u].l=l,a[u].r=r;
        if(l==r) { return ; }

        ls=idx++,rs=idx++;
        build(ls,l,mid); build(rs,mid+1,r);
    }

    void insert(int u,int d)
    {
        if(a[u].l==a[u].r)
        {
            a[u].data++;
            return ;
        }

        if(d<=mid) insert(ls,d);
        else        insert(rs,d);
        push_up(u);
    }
    void del(int u,int d)
    {
        if(a[u].l==a[u].r)
        {
            a[u].data--;
            return ;
        }
        if(d<=mid) del(ls,d);
        else        del(rs,d);
        push_up(u);
    }

        //最大数的排名
    int rank(int u,int d)
    {
        if(a[u].r<=d) return a[u].data;
        if(d<=mid) return rank(ls,d);
        else        return rank(rs,d)+rank(ls,d);
    }

    int kth(int u,int d)
    {
        if(a[u].l==a[u].r && d) return a[u].l;
        if(d<=a[ls].data) return kth(ls,d);
        else               return kth(rs,d-a[ls].data);
    }
}t;

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>q[i].opt>>q[i].data;
        pos.push_back(q[i].data);
    }
    pos.push_back(INT_MIN); pos.push_back(INT_MAX);
    sort(pos.begin(),pos.end()); pos.erase(unique(pos.begin(),pos.end()),pos.end());
    t.build(1,0,n+2);
    for(int i=1;i<=n;i++)
    {
        int tmp=upper_bound(pos.begin(),pos.end(),q[i].data)-pos.begin()-1;
        if(q[i].opt==1) t.insert(1,tmp);
        else if(q[i].opt==2) t.del(1,tmp);
        else if(q[i].opt==3) printf("%lld\n",t.rank(1,tmp-1)+1);
        else if(q[i].opt==4) printf("%lld\n",pos[t.kth(1,q[i].data)]);
        else
        {
            if(q[i].opt==5)
            {
                int rk=t.rank(1,tmp-1);
                printf("%lld\n",pos[t.kth(1,rk)]);
            }
            if(q[i].opt==6)
            {
                int rk=t.rank(1,tmp)+1;
                printf("%lld\n",pos[t.kth(1,rk)]);
            }
        }
    }

    return 0;
}

---

Tarjan

dfn[]	时间戳
low[]	能访问到的最小的 dfn[]

1. 缩点

   不如 Kosaraju

2. 割点 和 割边

   以下的边 $u \rightarrow i$ 均为 树边。

   • 割点

     若 u 为根且含有 两个及以上的 儿子，则 u 为割点。

     若 u 非根且存在儿子 i, 使得low[i]≥dfn[u] ，则 u 为割点。

   • 割边

     节点 u 存在儿子 i , 使得 low[i]>dfn[u] , 则边 $u \rightarrow i$ 为割边。

3. 点双 和 边双

   以下的边 $u \rightarrow i$ 均为 树边。

   点双和边双 缩完后均为树。

   • 点双

     若 u 存在儿子 i , 使得 low[i]>=dfn[u]，则 当前栈里在 i 之上的节点均在 u 所在的点双里。

     注意，割点存在于多个点双中。

     void tarjan(int u)
     {
        ...
        sta.push(u);
        for(int i:g[u])
        {
            ...
            if(!dfn[i])
            {
                tarjan(i),low[u]=min(low[u],low[i]);
                if(low[i]>=dfn[u])
                {
                    ++col; int v; do {
                        v=sta.top(); sta.pop();
                        dcc[col].push_back(v);
                    } while(v!=i);
                    dcc[col].push_back(u);
                }
            }
            ...
        }
     }

   • 边双

     先求割边。

     然后在不走桥的前提下 $dfs$ 遍历整张图，每个连通块均为边双。

     注意，每条边仅属于一个点双。

     void ECC(int u)
     {
         vis[u]=1,p[u]=col;
         for(int j(h[u]);j;j=ne[j])
         {
             int i=e[j];
             //  cnr[j]是判断 u->i 是否为割边
             if(!cnt[j] && !vis[i]) ECC(i);
         }
     }

例题

1. PUS

   线段树优化建图 + 差分约束 板子题

2. 最小公倍树

   i 向 i的倍数 联边。

   边数为 $\frac{len}{1} + \frac{len}{2} + \frac{len}{3} + …+ \frac{len}{len-1} + \frac{len}{len} = len ~ \times ~log_{len} $ 。

3. 宝石装箱

   首先考虑去除颜色限制。

   则 $i$ 与 $4n-i+1~(1\leq i\leq \frac{n}{2} )$ 配对一定可行，并将这些宝石所对应的颜色相连。

   又因为每颗宝石对度的贡献仅为1，所以总度为4，必定存在欧拉回路。

4. 狼人游戏

   首先一句话概括题意：

   算出何老板死的概率。 by myq

   进行缩点后，每一次询问的节点一定是没有前驱的节点。

   需要注意的是：

   • 每一轮选中的是入度为0的，最后一人可能可以使用排除法
   • 每一个人作为狼人的概率均为 $\frac{1}{n}$，因为 $\frac{n-siz1}{n}\times \frac{1}{n-siz1}=\frac{1}{n}$。