网络流

· · 算法·理论

链式前向星

前置内容：网络流所使用的数据结构

个人理解为带一个记录每个点最后一个边的head数组，和一个存边的链表，next表示这一个点的下一个边的位置

#include <iostream>
#include <cstring>
#define MAXN 1001
using namespace std;

struct Edge
{
    int next, to, w;
} edge[MAXN];

int n, m, s, t, head[MAXN], cnt;

void add(int u, int v, int w)
{
    edge[cnt].next = head[u];
    edge[cnt].to = v;
    edge[cnt].w = w;
    head[u] = cnt++;
}

int main()
{
    memset(head, -1, sizeof(head));
    cin >> n >> m >> s >> t;
    for(int x = 0; x < m; x++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    for(int x = 1; x <= n; x++)
    {
        for(int y = head[x]; y >= 0; y = edge[y].next) cout << y << " ";
        cout << endl;
    }
    return 0;
}

下面这篇文章讲得不错（

链式前向星

网络流

模板题：P3376

这里用的是Edmond-Karp(EK)算法，就是Ford-Fulkerson(FF)算法的bfs版本，效率高，码量不大，不过速度最快的还是Dinic算法（不会

大概就是建反向边，不断寻找增广路

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#define MAXN 10001
#define INF 0x7fffffff
#define LL long long
using namespace std;

struct Edge
{
    LL next, to, w;
} edge[MAXN];

LL n, m, s, t, head[MAXN], cnt = 1, last[MAXN], flow[MAXN];

void add(LL u, LL v, LL w)
{
    ++cnt;
    edge[cnt].next = head[u];
    edge[cnt].to = v;
    edge[cnt].w = w;
    head[u] = cnt;
}

LL bfs()
{
    memset(last, -1, sizeof(last));
    queue <LL> q;
    q.push(s);
    flow[s] = INF;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        //cout << u << " ";
        if(u == t) break;
        for(LL x = head[u]; x > 0; x = edge[x].next)
        {
            LL v = edge[x].to, w = edge[x].w;
            //cout << v << endl;
            if(w > 0 && last[v] == -1)
            {
                last[v] = x;
                flow[v] = min(flow[u], w);
                q.push(v);
            }
        }
    }
    return last[t] != -1;
}

LL EK()
{
    LL ans = 0;
    while(bfs())
    {
        ans += flow[t];
        //cout << "Flow:  " << flow[t] << endl;
        for(LL x = t; x != s; x = edge[last[x] ^ 1].to)
        {
            edge[last[x]].w -= flow[t];
            edge[last[x]^1].w += flow[t];
        }
    }
    return ans;
}

int main()
{
    //freopen("test.in", "r", stdin);
    memset(head, -1, sizeof(head));
    cin >> n >> m >> s >> t;
    for(LL x = 0; x < m; x++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, 0);
    }
    cout << EK() << endl;
    fclose(stdin);
    return 0;
}

板子题卡long long，但不卡EK

网络流详解