Contents
一些杂项
INF
图论题的INF表示两个点不连通,通常设为0x3f3f3f3f
,这样两者相加就不会溢出,当需要开long long
时通常设为0x3f3f3f3f3f3f3f3fLL
。
当然如果无负权值边的话也可以使用-1
,但需要特判
不推荐使用0x7fffffff
,虽然是int
的最大值,但是两者相加时会溢出
一些概念
- 点的度数
- 环
- DAG 有向无环图
拓扑排序
定义
对DAG的顶点进行排序,要求:1. 每个点出现且仅出现一次 2. 对于顶点对(u,v),若排序后u在v的前面,则不存在从v到u的路径
如果给定一个DAG,从i到j有边,则称j依赖于i;如果从i到j有路径,则称j间接依赖于i。
拓扑排序后,排在前面的节点不能依赖于排在后面的节点
算法实现
- 考虑将所有入度为0的点加入一个队列中
-
然后挨个点进行处理,设当前处理到u枚举其出边,设该边连着v,然后进行信息更新
-
由于u已处理过,所以相当于删除u,将v的入度-1
-
如果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;
尝试使用s到u的最短路加上边(u, v)的长度更新s到v的最短路
实现
- 起点作为已访问集合的第一个点,并更新相连的点的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,在同层图内移动就是普通移动,跨层移动就是买卖操作
拆点
遇到涉及到点权的最短路,可以将一个点拆为两个点,然后两个点之间边的权值为点权即可。
留言