網絡流最小割Dinic/最短路spfa（Barricade HDU5889）

題目連結

通過本題學習網絡流及較實用的dinic算法。

通過部落格了解了基本算法EK算法，及最大流最小割定理（最大流 = 最小割）

dinic就是EK的優化：

我們每次進行dfs增廣路時進行一次bfs

bool bfs(int s, int End)
{
    memset(l, 0, sizeof(l));
    queue<int> Q;
    Q.push(s);
    l[s] = 1;
    while(Q.size())
    {
        int u = Q.front();
        Q.pop();
        if (u == End) return 1;
        for (int i = Head1[u]; i != -1; i = e[i].Next)
        {
            int v = e[i].v;
            if (!l[v] && e[i].w)
            {
                l[v] = l[u] + 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
           

兩個作用

1.找通路，若從s到t不連通時，增廣路完畢，退出算法。

2.記錄最短通路，在進行增廣路時，隻延最短路即可。

判斷某邊屬于最短路：

l[v] == l[u] + 1

這裡l[k] 指的是k點至s的層數。

而對于這道題，敵人隻會走最短路徑，是以spfa跑一遍得到最短路，也可通過上述方法把屬于最短路的邊找出來。，然後用這些邊建一張新圖，最後跑一遍dinic

下面是ac代碼：

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define ll long long
#define INF 0x3f3f3f3f
#define N 100000+10
#define ll long long
using namespace std;
//%mmk
struct Node
{
    int v, w, d, Next;

    Node(int _v = 0, int _w = 0, int _d = 0) : v(_v), w(_w), d(_d){}

}e[N*4];

vector<vector<Node> > g;
int n, vis[N];
int dist[N];
int l[N];
int Head1[N], cnt1;

void Add1 (int u, int v, int w)
{
    e[cnt1].v = v;
    e[cnt1].w = w;
    e[cnt1].Next = Head1[u];
    Head1[u] = cnt1++;
}

void Init()
{
    g.clear();
    g.resize(n+1);
    memset(Head1, -1, sizeof(Head1));
    cnt1 = 0;
    for (int i = 0; i <= n; i++)
    {
        vis[i] = 0;
        dist[i] = INF;
    }
}
void spfa()
{
    dist[1] = 0;
    vis[1] = 1;
    queue<int> Q;
    Q.push(1);
    while(Q.size())
    {
        int p = Q.front();
        Q.pop();
        for (int i = 0, len = g[p].size(); i < len; i++)
        {
            int q = g[p][i].v;
            if (dist[q] >dist[p]+g[p][i].d)
            {
                dist[q] = dist[p] + g[p][i].d;
                if (!vis[q])
                {
                    vis[q] = 1;
                    Q.push(q);
                }
            }
        }
    }
}
bool bfs(int s, int End)
{
    memset(l, 0, sizeof(l));
    queue<int> Q;
    Q.push(s);
    l[s] = 1;
    while(Q.size())
    {
        int u = Q.front();
        Q.pop();
        if (u == End) return 1;
        for (int i = Head1[u]; i != -1; i = e[i].Next)
        {
            int v = e[i].v;
            if (!l[v] && e[i].w)
            {
                l[v] = l[u] + 1;
                Q.push(v);
            }
        }
    }
    return 0;
}

int dfs (int u, int MaxFlow, int End)
{
    if (u ==End) return MaxFlow;
    int uflow = 0;
    for (int j = Head1[u]; j != -1; j = e[j].Next)
    {
        int v = e[j].v;
        if (l[v] == l[u] + 1 && e[j].w)
        {
            int flow = min(e[j].w, MaxFlow - uflow);
            flow = dfs(v, flow, End);
            e[j].w -= flow;
            e[j^1].w += flow;
            uflow += flow;
            if (uflow == MaxFlow)
                break;
        }
    }
    if (uflow == 0)
        l[u] = 0;
    return uflow;
}

int Dinic()
{
    int MaxFlow = 0;
    while(bfs(1, n))
        MaxFlow += dfs(1, INF, n);
    return MaxFlow;
}

int main()
{
    int T, m, u, w, v;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        Init();
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            g[u].push_back(Node(v, w, 1));
            g[v].push_back(Node(u, w, 1));
        }
        spfa();
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0, len = g[i].size(); j < len; j++)
            {
                int p = g[i][j].v;
                if (dist[p] == dist[i] + g[i][j].d)
                {
                    Add1(i, p, g[i][j].w);
                    Add1(p, i, 0);
                }
            }
        }
        int ans = Dinic();
        printf("%d\n", ans);
    }
    return 0;
}