经验总结

  1. 首页 > 生活 > >

Day3 最短路 最小生成树 拓扑排序

生活百科

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\) 为该差分约束系统的一组解 。

    经验总结扩展阅读


    上一篇：认识 Redis client-output-buffer-limit 参数与源码分析

    下一篇：圣诞岛红蟹有毒吗