图论算法

2020-07-29 18:17:52


文章目录

  • 最短路算法
    • Floyd
    • SPFA
    • Dijkstra
  • 次短路算法
  • k短路算法
  • 差分约束
  • 找环
  • 拓扑排序

最短路算法

SPFA

关于SPFA,他死了

#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

#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(代码出处)
P2865 [USACO06NOV]Roadblocks G

#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短路算法

判断负环

差分约束

使用条件

当题目中的条件都满足形如 $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]倍杀测量者

例题

P1993 小 K 的农场

#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;
}

拓扑排序

应用:裸题,和贪心结合决定排队次序,无向图定向(跑一遍拓扑排序然后按照拓扑序给边定向,方向一定是从前面的点往后面的点连边)