Day3 最短路 最小生成树 拓扑排序
（一）最短路
一、多源最短路
从任意点出发到任意点的最短路
1. Floyd \(O(n^3)\)
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
Edge[i][j]=min(Edge[i][j],Edge[i][k]+Edge[k][j]);
2. 拓展：传递闭包
在图中，给定若干元素和若干对二元关系，且关系具有传递性。“通过传递性推导出尽量多的元素之间的关系”的问题称为传递闭包。
传递性：设 \(\odot\) 是定义在集合 \(S\) 上的二元关系，若对于任意 \(a,b,c \in S\)，只要有 \(a \odot b\) 且 \(b \odot c\)，就必然有 \(a \odot c\)，则称关系 \(\odot\) 具有传递性
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
can[i][j]|=can[i][k]&can[k][j];
二、单源最短路
从一个点出发到所有点的最短路
1. Dijkstra
①Dijkstra \(O(n^2)\)
void dijkstra(int x)
{
for(int i=1;i<=t;i++)
dis[i]=INF;
dis[x]=0,vis[x]=true;
for(int i=Link[x];i!=0;i=Edge[i].nxt)
{
int y=Edge[i].y;
dis[y]=Edge[i].vis;
}
for(int i=1;i<=t;i++)
{
int f,minn=INF+10;
for(int j=1;j<=t;j++)
{
if(!vis[j]&&dis[j]<minn)
{
minn=dis[j];
f=j;
}
}
vis[f]=true;
for(int i=Link[f];i!=0;i=Edge[i].nxt)
{
int y=Edge[i].y;
if(!vis[y]) dis[y]=min(dis[y],Edge[i].vis+dis[f]);
}
}
}
②堆优化 Dijkstra \(O(m \log n)\)
priority_queue<node> q;
bool operator < (node n1,node n2)
{
return n1.dis>n2.dis;
}
void dijkstra(int st)
{
for(int i=1;i<=n;i++)
dis[i]=INF;
dis[st]=0;
q.push({0,st});
while(!q.empty())
{
int x=q.top().i;
q.pop();
if(vis[x]) continue;
vis[x]=1;
for(int j=Link[x];j!=0;j=Edge[j].nxt)
{
int y=Edge[j].y,val=Edge[j].val;
if((long long)dis[x]+val<dis[y])
{
dis[y]=dis[x]+val;
q.push({dis[y],y});
}
}
}
}
2. SPFA \(O(km \sim nm)\)
解决负环判断/差分约束问题。
void SPFA(int st)
{
queue<int> q;
for(int i=1;i<=n;i++)
dis[i]=INF;
dis[st]=0;
q.push(st);
while(!q.empty())
{
int x=q.front();
q.pop();
vis[x]=false;
for(int i=Link[x];i;i=Edge[i].nxt)
{
int y=Edge[i].y,val=Edge[i].val;
if(dis[x]+val<dis[y])
{
dis[y]=dis[x]+val;
if(!vis[y])
{
q.push(y);
vis[y]=1;
}
}
}
}
}
3. 拓展：查分约束
差分约束系统是一种特殊的 \(N\) 元一次不等式组。
它包含 \(N\) 个变量 \(X_1 \sim X_N\) 以及 \(M\) 个约束条件，每个约束条件都是由两个变量作差构成的，形如 \(X_i-X_j \leq C_k\) ，其中 \(C_k\) 是常数。我们要解决的问题是：
求一组解 \(X_1 = a_1, X_2 = a_2,\cdots, X_N = a_N\)，使得所有约束条件得到满足。
我们把不等式 \(X_i-X_j\leq C_k\) 变为 \(X_i\leq X_j+C_k\) ，这和我们单源最短路里 \(dis[y]\leq dis[x]+z\) 非常相似。
**因此，可以把 \(X_i\) 看作有向图中的一个点 \(i\)，对于每个条件 \(X_i-X_j\leq C_k\)，从节点 \(j\) 向节点 \(i\) ，连一条长度为 \(C_k\) 的有向边。 **
如果 \(a_1,a_2,\cdots,a_n\) 是该差分约束系统的一组解，那么对于任意的常数 \(D\)，\(a_1+D,\cdots,a_n+D\) 显然也是该差分约束系统的一组解，因为这样做差后 \(D\) 刚好被消掉。
所以不妨先求一组负数解，假设 \(\forall x_i\leq 0\) ，添加一个 \(0\) 号节点，\(x_0=0\) ，即有 \(x_i-x_0\leq 0\)，
设 \(dis[0]=0\)，从 \(0\) 开始跑单源最短路，若图中存在负环，则给定的差分约束系统无解；否则， \(x_i=dis_i\) 为该差分约束系统的一组解。
Example:
若\(x_1-x_2 \leq3\) , \(2\) 连 \(1\) 有一条权值为 \(3\) 的边，那么
dis[2] =0,dis[1]=0为一组解。若 \(x_1-x_2\leq-3\) ， \(2\) 连 \(1\) 有一条权值为 \(-3\) 的边，那么
dis[2]=0,dis[1]=-3就是一组解。如果有正环（权值和为正），比如 \(x_1-x_2<1,x_2-x_3<1,x_3-x_1<1\) 得到 \(0<3\)，这是可以的。
如果有负环（权值和为负），比如 \(x_1-x_2<-1,x_2-x_3<-1,x_3-x_1<-1\) 得到 \(0<-3\)，这是不可能的。
于是差分约束系统是无解的。
因此，通常由于负权的存在， 差分约束系统 采用 SPFA 来求解，以及判断负环。
4. 总结
单源最短路首选稳定的 堆优化Dijkstra ，其次是 SPFA。
很多时候简单的 \(\text{SPFA}\) 甚至更快，但我们知道 \(\text{Dijkstra}\) 是不能处理有负权边的图的。
所以有负权的时候，我们常用 SPFA 。
（二）最小生成树
一、Kruskal \(O(mlogn)\)
将边排序，利用并查集，从小到大加入能够联通新的联通分量的边。
void Kruskal()
{
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
int fx,fy;
fx=getfather(a[i].a);
fy=getfather(a[i].b);
if(fx!=fy)
{
merge(fx,fy);
flag[i]=1;
if(++cnt==n-1) break;
}
}
}
二、Prim \(O((n+m)logn)\)
将点划分，利用 堆（优先队列） 以生成树到散点的边的边权为关键字，从小到大加入点。
void Prim()
{
for(int i=1;i<=n;i++)
dis[i]=Edge[1][i];
vis[1]=true;
for(int i=1;i<=n-1;i++)
{
int minn=INF,f;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&dis[j]<minn)
{
minn=dis[j];
f=j;
}
}
vis[f]=true;
ans+=minn;
for(int j=1;j<=n;j++)
if(!vis[j]&&Edge[f][j]&&dis[j]>Edge[f][j])
dis[j]=Edge[f][j];
}
}
（三）拓扑排序
给一个图的所有点排序，使得排在前面的点不依赖于后边。
用于判断图中是否有环，判断图是否是一个链（都是简单 bfs）。
算法实现
- 维护一个队列，队列中是所有入度为 \(0\) 的点，每次取出一个点（并按次序标号）扫描所有的出边并将这些边删除（将这些点入度\(-1\)），出现新的入度为 \(0\) 的点则加入队，不断重复直到队列为空。
- 点按出队顺序排就是一个拓扑序列，这个序列满足前面的点一定不能被后边的点到达。
void topsort()
{
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=Link[x];i;i=Edge[i].nxt)
{
int y=Edge[i].y;
f[y]+=f[x]%Mod;
ind[y]--;
if(!ind[y]) q.push(y);
}
}
}
标签：
留言评论