Day1：

emming，高中部集训在春节前要上5天，春节后上2天（如果我没记错的话QAQ)。

学校的电脑系统重装了一遍，把万恶的冰点还原（^-^)和教师监控系统（但是我怎么接老师课件啊QAQ）刷掉了，嘿嘿嘿。

以上是废话。

今天课程表：

2019.1.23

上午

• 数学：排列组合、概率论、素数筛、快速幂、欧几里得算法、扩欧。

下午

• 图论：基本概念、储存方式、遍历方式、拓扑排序、最短路。

晚上

• 考试

笔记

1. 概率论

• 概率空间：

  • 定义：一般我们在一个概率空间内探讨问题，概率空间即所有可能事件的集合，每一件事件有确定的概率。
  • 性质：$P(AB)$表示$A$,$B$同时发生的概率，$P(\frac{A}{B})$表示在$B$已经发生的情况下，A发生的概率，又叫条件概率。

• 期望：

  • 定义：随机变量$X$，概率空间中的事件为变量的取值情况，$X$的期望$E(X)=∑p_i x_i$，即所有取值的加权平均，意义为对一个随机变量进行观测后的可能值叠加。

  • 期望的线性性：

    1. $E(X+Y)=E(X)+E(Y)$
    2. 若$X$,$Y$两个变量独立，则$E(XY)=E(X)E(Y)$

2.拓扑排序

• 对象：有向无环图$（Directed　Acyclic　Graph，DAG）$。
• 作用：将一个图G中的所有顶点排序成一个序列，使得对于图中每一条边$（u,v)$，满足$u$在序列中排在$v$的前面（便利顺序），这个序列被称为图的拓扑序列。

• 算法：

  1. 从图中任选一个入度为 0 的顶点，加入拓扑序列末端
  2. 删除这个顶点及其所有出边
  3. 回到 S1 继续执行，直到图中没有顶点
• 结论：任意 $DAG$可经由拓扑排序化为合法的拓扑序列。

• 拓展：

  1. 可以用在图中检验是否含有环，方法是拓扑排序后检查是否有未标记完的顶点。如果有，就说明有环，因为环使得不会有一个顶点入度为0。
  2. 时间复杂度:

  邻接表：$O(n+m)$

  邻接矩阵：$O(n^2)$

• 例题：$【CodeVS】$2883 奇怪的梦境

  • 分析：判断是否可以按下全部按钮就是判段有向图中是否存在环，使用拓扑排序可以判断。

  • $Code$：

    #include <iostream>
    #include <cstdio>
    using namespace std;
    struct node{
        int v,next;//使用邻接表存边
    }edge[25005];
    int n,m,head[10005],cnt,deg[10005];
    bool book[10005];
    inline void add(int u,int v){
        cnt++;
        edge[cnt].v=v;
        edge[cnt].next=head[u];
        head[u]=cnt;
        return;
    }
    int main(){
        int a,b;
        scanf("%d%d",&n,&m);
        for (int i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            add(a,b);
            deg[b]++;
        }
        for (int i=1;i<=n;i++){
            int start=-1;
            for (int j=1;j<=n;j++)
                if (!book[j]&&deg[j]==0){
                    start=j;
                    book[j]=true;
                    break;
                }
            if (start==-1){
                cout <<"T_T"<<endl<<n-i+1<<endl;
                return 0;
            }
            for (int j=head[start];j!=0;j=edge[j].next)
                deg[edge[j].v]--;
        }
        cout <<"o(∩_∩)o"<<endl;
        return 0;
    }

3. 最短路

1. 单源最短路$（Single-Source　Shortest　Paths）$,对于给定带权图（有向或无向），计算从源点$s$到其它所有顶点的最短路径。

   • “三角形性质”：设源点s到u, v最短路径长度分别为 $dis[u], dis[v]，u$与$v$间距离为 $len[u][v]$，则有：$dis[u] + len[u][v] >= dis[v]$。

   • 松弛：若在处理过程中，有两点$u, v$不满足“三角形性质”，则可作改进：

     if (dis[u] + len[u][v] < dis[v])
         dis[v] = dis[u] + len[u][v];

   • $Dijkstra$算法:

     • 算法：将图$G$中顶点分为两个集合$A$, $B$，$A$由已求出最短路的顶点组成，$B$由其他顶点组成，初始时$A$为空，记源点$s$到每个点最短路径为$dis[v]$，初始时$dis[s] = 0$，其余点$dis[v] = INF$。

       1. 从$B$集合中取出一个当前距离$s$最近的点$v$
       2. 将$v$从$B$中剔除、加入$A$集合，并对与$v$相邻的顶点试作松弛
       3. 若 $A = V$，则算法结束​，否则转至第1步。
     • 伪代码：

     void dijkstra(int s){
         置dis初值;
         循环n次{
              找到B集合中dis最小的点v;
               将v从B中剔除、加入A;
               用v对其相邻点试作松弛;
         }
     }

 * 时间复杂度
   1. $O(n^2)$：使用循环确定松弛顶点。
   2. $O((n+m)\log m)$：使用**优先队列**。
 * 对象：
   1. 有向图、无向图（无向图看做两点两条有向边）
   2. 有环或无环
   3. **不可有负权边**

1. 多源最短路$（Multiple-Source　Shortest　Paths）$：对于给定带权图（有向或无向），计算所有顶点间两两最短路径。

   • $Floyd$算法

     • 算法：有一些$dp$的思想->_<-，$f_k[i][j]$表示从$i$到$j$只经过前$k$个点的最短路径。初始状态：$f_0[i][i]=0$,$f_0[i][j]=(u,v)\in E?dis(u,v):INF$。

       • 转移方程：$f_k [i][j]=min⁡(f_{k-1} [i][j],f_{k-1} [i][k]+f_{k-1} [k][j])$，$f_n$ 即所求。

       • $Floyd$算法核心代码：

         for (int k = 1; k <= n; k++)
             for (int i = 1; i <= n; i++)
                 for (int j = 1; j <= n; j++)
                     f[i][j] = min(f[i][j], f[i][k] + f[k][j]);

   * 时间复杂度：$O(n^3)$

总结

今天的考试有点难，或者说码量比较大，说明我还是太菜了QAQ

本文作者：Snowflake_Pink
本文链接：https://snowflake.pink/archives/7/
最后修改时间：2020-04-13 11:18:33
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！