Minimum cutting Dinic / shortest spfa of network flow (barricade hdu5889)

Title Link
This paper studies network flow and dinic algorithm.
The basic algorithm EK algorithm and the minimum cut theorem of maximum flow (maximum flow = minimum cut) are known through blog.

dinic is the optimization of EK:
We do bfs every time we do dfs augmentation.

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

Two functions
1. Find the path. If the path is not connected from s to t, the augmented path is completed and exit the algorithm.
2. Record the shortest path. When widening the path, only extend the shortest path.

Judge that one side belongs to the shortest circuit:

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

Here, l[k] refers to the number of layers from K point to s.
For this problem, the enemy will only take the shortest path, so spfa can run once to get the shortest path, or find out the shortest path through the above methods. , then build a new picture with these edges, and run dinic for the last time

Here is the ac Code:

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

Tags: network

Posted on Fri, 01 Nov 2019 14:08:28 -0700 by Petrushka