常州集训Day6

Posted on By 王, 传智 常州集训Day6无评论

早上

老师讲了图论

包括

图论的基本概念

§ V——图中所有顶点(vertex)的集合，顶点通常用数字0..n-1表示， 顶点的个数称为阶（n阶图），记为|V|。

§ E——图中顶点之间所有边(edge)的集合，边用(u,v) 表示，边数 记为|E|。 § 对于某一条边 (u,v)∈E：

-我们说，u和v是邻接的(adjacent)

-我们说，边e和u、v关联(incident)

§ 无向图与有向图：无向边(u,v)=(v,u)，有向边 （弧）与不一样，入边与出边。

度

度：入度与出度。

奇点、偶点：无向图中顶点度的奇偶性，一笔画问题的条件？

完全图：每一对顶点间都有边相连的的无向图，总边数多少？

稀疏图与稠密图：边与顶点的数量关系。

子图：取出若干顶点和他们相关的边，构成的新图。

补图：图中所有顶点和所有能使该图成为完全图的添加边所组成的图。

逆图：把一个有向图的每条边都反向得到的有向图。

自环(self cycle)：若一条边的两个顶点为同一顶点，中图的4。 n 一条路径(path)是一个顶点序列, 其上的相邻顶点在图上是邻接的，上图： B-A-D-C，下图：1-2-4-5-3。

如果顶点和边都不重复出现, 则称为简单路径(simple path)。如果除了 起点和终点相同外没有重复顶点和边, 称为圈(cycle，回路、环)，下图： 2-4-3-2和4-5-4。

简单图：没有环、且没有多重边。

不相交路径(disjoint path)：表示除了起点和终点，没有公共顶点的路 径。更严格地： -任意顶点都不相同的叫严格不相交路径(vertex-disjoint path) -同理，可以定义边不相交路径(edge-disjoint path)

连通：从顶点x到顶点y有路径相连(有向图边的方向要一致)，称x和y连通。

连通图：无向图任意两个顶点都是连通的。

强连通图：有向图任意两个顶点x,y间都存在着从x到y和从y到x的路径。

还讲了图的储存方式

1、邻接矩阵：|V|*|V|的二维数组A。A[i][j]=0，若不存在边 (i，j)；A[i][j]=1，若存在边(i，j)。

2、边集数组 边号起点终点

• 每条边存储为一个数组元素。
• 还可以根据需要加上边权。
• 以边为核心

3、邻接表：每个顶点的所有邻接点存成一个链表，再把所有起点存储到 一个数组中。

邻接表

１、邻接表的定义和建立

２、邻接表的数组实现

３、邻接表的vector实现

４、邻接表的map实现

链式前向星

深度优先遍历(DFS)

边的分类

１、树边(Tree Edges, T边): v通过边(u, v)发现

２ 后向边(Back Edges, B边): u是v的后代；

３、前向边(Forward Edges, F边): v是u的后代；

４、交叉边(Cross Edges, C边): 其他边，可以连接同一个DFS树中 没有后代关系的两个顶点, 也可以连接不同DFS树中的顶点。

DFS应用举例

１、欧拉路（一笔画）：从图中某个点出发，遍历整个图，图中每条边通过且只通 过一次

２、欧拉回路：起点和终点相同的欧拉路。

３、 欧拉路问题有两个：是否存在欧拉路、打印欧拉路。

４、欧拉路的存在性判断： 无向连通图的判断条件：如果图中的点全都是偶点，则存在欧拉回路，任意 点都可以作为起点、终点。如果只有两个奇点，则存在欧拉路，其中一个奇 点是起点、另一个为终点。不可能出现奇数个奇点的无向图

５、有向连通图的判断条件：把一个点的入度记为1、出度记为-1，整个点所有 出度和入度之和就是它的度。一个有向图存在欧拉回路的条件当且仅当该图 所有点的度数为0.存在欧拉路的条件是只有一个度数为1的点（就是起点）、 一个度数为-1的点（就是终点）、其他点的度数都是0。

６、打印欧拉路：DFS。

下午

这次考试并没有在犯低级错误，第一题１００分，第三题７０分（超时了三个）
> #include<bits/stdc++.h>
using namespace std;
int x,y,n;
long long ans=0;
priority_queue<int>s;
int main() {
    freopen("battery.in","r",stdin);
    freopen("battery.out","w",stdout);
    cin>>n;

    for(int i=1; i<=n; i++) {
        cin>>x;
        s.push(x);
    }
    while(s.size()>1) {
        x=s.top();
        s.pop();
        y=s.top();
        s.pop();
        ans+=y;
        if(x!=y) {
            s.push(x-y);
        }
    }
    cout<<ans;
    return 0;
}

最后一次考试成绩也只能算一般，但是相对于昨天还是有进步的。
下次一定要更加努力，在学习中也不能犯低级错误！！！！

训练日志

发表回复