一些杂项

INF

图论题的INF表示两个点不连通,通常设为0x3f3f3f3f,这样两者相加就不会溢出,当需要开long long时通常设为0x3f3f3f3f3f3f3f3fLL

当然如果无负权值边的话也可以使用-1,但需要特判

不推荐使用0x7fffffff,虽然是int的最大值,但是两者相加时会溢出

一些概念

  • 点的度数
  • DAG 有向无环图

拓扑排序

定义

对DAG的顶点进行排序,要求:1. 每个点出现且仅出现一次 2. 对于顶点对(u,v),若排序后uv的前面,则不存在从vu的路径

如果给定一个DAG,从ij有边,则称j依赖于i;如果从ij有路径,则称j间接依赖于i

拓扑排序后,排在前面的节点不能依赖于排在后面的节点

算法实现

  1. 考虑将所有入度为0的点加入一个队列中

  2. 然后挨个点进行处理,设当前处理到u枚举其出边,设该边连着v,然后进行信息更新

  3. 由于u已处理过,所以相当于删除u,将v的入度-1

  4. 如果v的入度为0了,加入队列

偏序关系

从自反性,对称性,传递性三个方面考虑集合的某个关系

类似小于等于

  • $\forall a\in S,a\leq a$
  • $\forall a,b\in S$,$a\leq b$且$b\leq a$,则$a=b$
  • $\forall a,b,c\in S$,$a\leq b$且$b\leq c$,则$a\leq c$

类似小于

  • $\forall a\in S, a \not < a$
  • $\forall a,b\in S$,$ a < b $,则$ b \not < a$
  • $\forall a,b,c\in S$,$ a < b $且 $ b < c $,则$ a < c $

这类关系称为偏序关系,可以将集合中元素建点,将这些关系建成有向边变成图论问题,然后通过拓扑排序等有向图算法求解

最小生成树

一些定义

  • 连通图:任意两点间存在路径

  • 树:以下定义等价:

    • 任意两点间只存在一条路径的图
    • 无环的连通图
    • $n$个点$n-1$条边的连通图
    • $n$个点$n-1$条边 , 无环的图
  • 子图:图G’称作图G的子图如果V(G’) \sube V(G)以及E(G’) \sube E(G)

    也就是从原图中选出一些点以及和一些边组成的新的图

  • 生成子图:指满足条件V(G’)=V(G)G的子图G’

    也就是选出所有的点和一些边组成的新的图,生成树则是指子图G’是一颗树

最小生成树

对于带权图,权值和最小的生成树。

最小瓶颈生成树:对于带权图,最大权值最小的生成树,最小生成树一定是最小瓶颈生成树

算法:Prim或者Kruskal算法,推荐后者,无需建图,复杂度都为O(m\log n)

Prim

  • 随意选取一个点作为已访问集合的第一个点,并将所有相连的边加入堆中

    从堆中找到最小的连接集合内和集合外点的边,将边加入最小生成树中

    将集合外点标记为已访问,并将相连边加入堆

  • 重复以上过程直到所有点都在访问集合中

Kruskal

  • 将边按照权值排序

  • 依次枚举每一条边,若连接的两点不连通则加入最小生成树中

  • 使用并查集维护连通性

最短路

所有算法概述

  • Floyd:求多源最短路,可以求出所有点对间的最短路径,时间复杂度O(n^3)
  • Dijkstra(/’daikstra/):单源最短路,求某点到所有点的最短路,时间复杂度O(n^2),优化后O(m\log n)无法处理负权边
  • SPFA(队列优化的Bellman-Ford算法):单源最短路,时间复杂度最坏O(nm)容易被卡可以处理负权边

Floyd

本质是DP

d[i][j][k]为从i到j,仅通过编号为1-k的中间节点的最短路距离

转移方程为d[i][j][k]=min(d[i][j][k-1], d[i][j][k-1]+d[k][j][k-1]),理解:不走k的话就是d[i][j][k-1],走k的话分为两段加起来就是d[i][j][k-1]+d[k][j][k-1]

初始值为d[i][j][0]为两点之间边的权值,未联通为INF

从1到n枚举k,然后枚举(i, j),为了方便可以不开第三维,在原地迭代

int d[MAXN][MAXN];

void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j && i != k && j != k)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

Dijkstra

维护一个dis[maxn]数组,dis[i]代表从起点到i的最短路长度

dis[s]=0,其余为INF

松弛操作

通过某条路径更新dis[v]的值

if(dis[v]>dis[u]+e.dist)
        dis[v]=dis[u]+e.dist;

尝试使用su的最短路加上边(u, v)的长度更新sv的最短路

实现

  • 起点作为已访问集合的第一个点,并更新相连的点的dis

  • 找到未被访问的dis最小的点,标记访问,用这个点更新相连的点dis

  • 重复上述过程直到所有的点均被访问

第二步中找到未被访问的dis最小的点若使用堆来优化的话时间复杂度将为O(m\log n)

priority_queue<pair<int,int>, vector<pair<int,int> >,greater<pair<int,int> > > q;
bool vis[maxn];
int d[maxn];

void dijkstra()
{
    memset(d,0x3f3f3f3f,sizeof(d));
    d[s]=0;
    q.push(make_pair(0,s));//pair的首元素是dis,第二个元素是点的编号
    while (!q.empty())
    {
        int now=q.top().second;
        q.pop();
        if(!vis[now])
        {
            vis[now]=1;
            for(auto &e:g[now])//遍历每一条边
            {
                if(d[e.to]>d[now]+e.dist)//松弛操作
                {
                    d[e.to]=d[now]+e.dist;
                    q.push(make_pair(d[e.to],e.to));
                }
            }
        }
    }
    return;
}

SPFA

Bellman-Ford:对整张图进行n-1次松弛,每次枚举每条边进行松弛,最后一定能得到最优解

SPFA在上述过程中避免无意义的松弛

只有成功的松弛操作才会对那个点产生影响,所以使用队列维护等待松弛的点,每次取出一个点进行松弛,对于所有松弛成功的点加入队列

判负环:如果某个点松弛了第n次,说明存在负环

queue<int> q;
bool inq[maxn];
int d[maxn];

void spfa()
{
    memset(d,0x3f3f3f3f,sizeof(d));
    q.push(s);
    inq[s]=1;//一定记得维护inq数组
    d[s]=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        inq[now]=0;
        for(auto &i:g[now])//遍历每一条边
        {
            int to=i.to,dist=i.dist;
            if(d[now]+dist<d[to])//松弛
            {
                d[to]=d[now]+dist;
                if(!inq[to])//如果不在队列中
                {
                    inq[to]=1;
                    q.push(to);//标记后加入队列
                }
            }
        }
    }
}

一些奇技淫巧

分层图

将一张图复制成若干层,并在这些图之间建立连边,然后照跑最短路

例题:P1073

我们可以考虑将图复制为三层,第一层到第二层之间将各点相连权值设为买的费用,第二层到第三层之间将各点相连权值设为卖的费用的负值,这样就可以模拟出买卖的操作,然后在同层图中边权都设为0,在同层图内移动就是普通移动,跨层移动就是买卖操作

拆点

遇到涉及到点权的最短路,可以将一个点拆为两个点,然后两个点之间边的权值为点权即可。

最后修改日期:2020年2月8日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。