图论算法
sdxjzsq
2020-07-29 18:17:52
# 文章目录
- 最短路算法
- Floyd
- SPFA
- Dijkstra
- 次短路算法
- k短路算法
- 差分约束
- 找环
- 拓扑排序
# 最短路算法
## SPFA
~~关于SPFA，他死了~~
``` cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005, maxm = 500005;
long long n, m, s;
int top = 0, head[maxn];
int inq[maxn], dist[maxn];
struct node
{
long long to, next, v;
} edge[maxm];
inline void addedge(long long fr, long long to, long long val)
{
edge[++top].to = to;
edge[top].v = val;
edge[top].next = head[fr];
head[fr] = top;
return;
}
queue<int> Q;
inline void spfa(int s)
{
memset(inq, 0, sizeof(inq));
for (register int i = 1; i <= n; i++) dist[i] = 2147483647; //若题目数据超过int，请使用0x3f3f3f3f3f3f3f3f
Q.push(s), dist[s] = 0, inq[s] = 1;
while (!Q.empty())
{
int u = Q.front();
Q.pop(), inq[u] = 0;
for (register int i = head[u], v, w; i; i = edge[i].next)
{
w = edge[i].to, v = edge[i].v;
if (dist[w] > dist[u] + v)
{
dist[w] = dist[u] + v;
if (!inq[w]) Q.push(w), inq[w] = 1;
}
}
}
}
int main()
{
scanf("%lld%lld%lld", &n, &m, &s);
for (register int i = 1, u, v, w; i <= m; i++) scanf("%lld%lld%lld", &u, &v, &w), addedge(u, v, w);
spfa(s);
for (register int i = 1; i <= n; ++i) printf("%lld ", dist[i]);
return 0;
}
```
## Dijkstra
``` cpp
#include <cstdio>
#include <queue>
using namespace std;
const int maxn = 1e5 + 7;
long long n, m, s;
inline long long rd()
{
char ch = getchar();
long long s = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s;
}
int head[maxn], top = 0;
struct node
{
long long to, next, v;
} edge[maxn << 1];
inline void addedge(int fr, int to, int val)
{
edge[++top].to = to;
edge[top].next = head[fr];
head[fr] = top;
edge[top].v = val;
return;
}
int dist[maxn];
struct pd
{
long long u, v;
bool operator<(const pd rhs) const { return v > rhs.v; }
};
priority_queue<pd> Q;
inline void dijkstra(int s)
{
for (register int i = 1; i <= n; i++) dist[i] = 2147483647;
dist[s] = 0, Q.push((pd){s, dist[s]});
while (!Q.empty())
{
pd t = Q.top();
Q.pop();
if (t.v != dist[t.u]) continue;
for (register int i = head[t.u]; i; i = edge[i].next)
if (t.v + edge[i].v < dist[edge[i].to])
dist[edge[i].to] = t.v + edge[i].v, Q.push((pd){edge[i].to, dist[edge[i].to]});
}
return;
}
int main()
{
scanf("%d%d%d", &n, &m, &s);
for (int i = 1, x, y, z; i <= m; i++) x = rd(), y = rd(), z = rd(), addedge(x, y, z);
dijkstra(s);
for (register int i = 1; i <= n; i++) printf("%d ", dist[i]);
return 0;
}
```
# 次短路算法
模板题：
[HDU6181 Two Paths](http://acm.hdu.edu.cn/showproblem.php?pid=6181)(代码出处)
[P2865 [USACO06NOV]Roadblocks G](https://www.luogu.com.cn/problem/P2865)
``` cpp
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
const long long maxn = 100005;
long long n, r, t, head[maxn], top, dist[2][maxn];
struct node
{
long long to, v, next;
} edge[maxn << 1];
inline void addedge(long long fr, long long to, long long val)
{
edge[++top].to = to;
edge[top].next = head[fr];
head[fr] = top;
edge[top].v = val;
return;
}
struct pd
{
long long u, d;
inline bool operator<(const pd &rhs) const { return d > rhs.d; }
};
std::priority_queue<pd> Q;
inline void dijkstra(int s)
{
memset(dist, 0x3f, sizeof(dist));
Q.push((pd){s, 0});
dist[0][s] = 0;
while (!Q.empty())
{
pd x = Q.top();
Q.pop();
if (x.d > dist[1][x.u]) continue;
for (int i = head[x.u]; i; i = edge[i].next)
{
long long w = edge[i].to, v = edge[i].v;
if (dist[0][w] >= x.d + v) //严格次短路去掉=号即可
dist[1][w] = dist[0][w], dist[0][w] = x.d + v, Q.push((pd){w, dist[0][w]});
else if (dist[0][w] < x.d + v && dist[1][w] > x.d + v)
dist[1][w] = x.d + v, Q.push((pd){w, dist[1][w]});
if (dist[1][w] > dist[1][x.u] + v) dist[1][w] = dist[1][x.u] + v, Q.push((pd){w, dist[1][w]});
}
}
}
int main()
{
for (scanf("%lld", &t); t--;)
{
scanf("%lld%lld", &n, &r), top = 0;
for (long long i = 1; i <= n; ++i) head[i] = 0;
for (register long long i = 1, u, v, w; i <= r; i++)
scanf("%lld%lld%lld", &u, &w, &v), addedge(u, w, v), addedge(w, u, v);
dijkstra(1);
printf("%lld\n", dist[1][n]);
}
return 0;
}
```
# k短路算法
``` cpp
```
# 判断负环
# 差分约束
#### 使用条件
当题目中的条件都满足形如 $x_i-x_j\le c_k$ 的不等式，便可以使用差分约束来求解满足所有不等式的 $x$ 最小解或判断不等式条件是否存在矛盾。
#### 思想
对条件进行变形： $x_i\le x_j+c_k$ ，可以发现这和最短路中的三角不等式 $dist[i]\le dist[j]+edge[i][j]$ 极为相似，因此我们就可以把条件转化为图上的边，也就是从 $j$ 到 $i$ 有一条长度为 $c_k$ 的边，然后跑一边最短路，则最短路的答案数组 $dist$ 就是能够让所有 $x$ 都满足条件的最小解。
因为可能会插入负边，所以应该用SPFA或Bellman-Ford算法求最短路。
如果图中存在负环，则说明题目条件存在矛盾。
（另一种思想是，将不等式写成 $x_i-x_j\ge c_k$ 的形式，然后从 $x_j$ 向 $x_i$ 连一条长度为 $c_k$ 的边，跑一边spfa求最常路，如果出现正环则无解。）（刚好反着）
在实际应用中，如果点本身有点权，也就相当于 $x_i=v$ ，因此可以建立一个点 $n+1$ 作为 $0$ 点($x_{n+1}=0$)，并利用 $x_i-x_{n+1}(0)\le v$ 和 $x_i-x_{n+1}(0)\ge v$ 连 $x_{n+1}$ 到 $x_i$ 长度为 $v$ 的边和 $x_i$ 到 $x_{n+1}$ 长度为 $-v$ 的边。（应用见[P4926 [1007]倍杀测量者](https://www.luogu.com.cn/problem/P4926)）
#### 例题
[P1993 小 K 的农场](https://www.luogu.com.cn/problem/P1993)
```cpp
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 5005;
int n, m, head[maxn], top;
struct node
{
int v, to, next;
} edge[maxn << 2];
inline void addedge(int x, int y, int v)
{
edge[++top].to = y;
edge[top].v = v;
edge[top].next = head[x];
head[x] = top;
}
int inq[maxn], cnt[maxn];
long long dist[maxn];
queue<int> Q;
inline bool spfa()
{
memset(dist, 0x3f, sizeof(dist));
memset(cnt, 0, sizeof(cnt));
dist[n + 1] = 0, inq[n + 1] = 1, cnt[n + 1] = 0, Q.push(n + 1);
while (!Q.empty())
{
int x = Q.front();
Q.pop(), inq[x] = 0;
for (int i = head[x]; i; i = edge[i].next)
{
if (dist[edge[i].to] > dist[x] + edge[i].v)
{
dist[edge[i].to] = dist[x] + edge[i].v;
if (!inq[edge[i].to])
{
inq[edge[i].to] = 1, Q.push(edge[i].to), ++cnt[edge[i].to];
if (cnt[edge[i].to] >= n) return false;
}
}
}
}
return true;
}
int main()
{
scanf("%d%d", &n, &m), top = 0;
memset(head, 0, sizeof(head));
for (int i = 1, x, a, b; i <= m; ++i)
{
scanf("%d", &x);
if (x == 1)
scanf("%d%d%d", &a, &b, &x), addedge(a, b, -x); // b-a<=-x
else if (x == 2)
scanf("%d%d%d", &a, &b, &x), addedge(b, a, x); // a-b<=x
else
scanf("%d%d", &a, &b), addedge(a, b, 0), addedge(b, a, 0); // a==b<=>a-b<=0&&b-a<=0
}
for (int i = 1; i <= n; ++i) addedge(n + 1, i, 0); // n+1为超级源点
puts(spfa() ? "Yes" : "No");
return 0;
}
```
### 拓扑排序
应用：裸题，和贪心结合决定排队次序，无向图定向（跑一遍拓扑排序然后按照拓扑序给边定向，方向一定是从前面的点往后面的点连边）