最大流 && 最小费用最大流模板

分类: IT文章 • 2024-09-05 09:31:31

模板从这里搬运，链接博客还有很多网络流题集题解参考。

最大流模板 ( 可处理重边 )

const int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;

struct Edge
{
    int from,to,cap,flow;
    Edge(){}
    Edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){}
};

struct Dinic
{
    int n,m,s,t;            //结点数,边数(包括反向弧),源点与汇点编号
    vector<Edge> edges;     //边表 edges[e]和edges[e^1]互为反向弧
    vector<int> G[maxn];    //邻接表,G[i][j]表示结点i的第j条边在e数组中的序号
    bool vis[maxn];         //BFS使用,标记一个节点是否被遍历过
    int d[maxn];            //d[i]表从起点s到i点的距离(层次)
    int cur[maxn];          //cur[i]表当前正访问i节点的第cur[i]条弧

    void init(int n,int s,int t)
    {
        this->n=n,this->s=s,this->t=t;
        for(int i=0;i<=n;i++) G[i].clear();
        edges.clear();
    }

    void AddEdge(int from,int to,int cap)
    {
        edges.push_back( Edge(from,to,cap,0) );
        edges.push_back( Edge(to,from,0,0) );
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BFS()
    {
        memset(vis,0,sizeof(vis));
        queue<int> Q;//用来保存节点编号的
        Q.push(s);
        d[s]=0;
        vis[s]=true;
        while(!Q.empty())
        {
            int x=Q.front(); Q.pop();
            for(int i=0; i<G[x].size(); i++)
            {
                Edge& e=edges[G[x][i]];
                if(!vis[e.to] && e.cap>e.flow)
                {
                    vis[e.to]=true;
                    d[e.to] = d[x]+1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    //a表示从s到x目前为止所有弧的最小残量
    //flow表示从x到t的最小残量
    int DFS(int x,int a)
    {
        if(x==t || a==0)return a;
        int flow=0,f;//flow用来记录从x到t的最小残量
        for(int& i=cur[x]; i<G[x].size(); i++)
        {
            Edge& e=edges[G[x][i]];
            if(d[x]+1==d[e.to] && (f=DFS( e.to,min(a,e.cap-e.flow) ) )>0 )
            {
                e.flow +=f;
                edges[G[x][i]^1].flow -=f;
                flow += f;
                a -= f;
                if(a==0) break;
            }
        }
        if(!flow) d[x] = -1;///炸点优化
        return flow;
    }

    int Maxflow()
    {
        int flow=0;
        while(BFS())
        {
            memset(cur,0,sizeof(cur));
            flow += DFS(s,INF);
        }
        return flow;
    }
}DC;

Dinic

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1210;
const int maxm = 240005;///边要是题目规定的两倍
const int INF = 0x3f3f3f3f;

struct edge{ int to,cap,tot,rev; };
struct DINIC{
    int n,m;
    edge w[maxm];
    int fr[maxm];
    int num[maxn],cur[maxn],first[maxn];
    edge e[maxm];
    void init(int n){
        memset(cur,0,sizeof(cur));
        this->n=n;
        m=0;
    }
    void AddEdge(int from,int to,int cap){
        w[++m]=(edge){to,cap};
        num[from]++,fr[m]=from;
        w[++m]=(edge){from,0};
        num[to]++,fr[m]=to;
    }
    void prepare(){
        first[1]=1;
        for(int i=2;i<=n;i++)
            first[i]=first[i-1]+num[i-1];
        for(int i=1;i<n;i++)
            num[i]=first[i+1]-1;
        num[n]=m;
        for(int i=1;i<=m;i++){
            e[first[fr[i]]+(cur[fr[i]]++)]=w[i];

            if (!(i%2)){
                e[first[fr[i]]+cur[fr[i]]-1].rev=first[w[i].to]+cur[w[i].to]-1;
                e[first[w[i].to]+cur[w[i].to]-1].rev=first[fr[i]]+cur[fr[i]]-1;
            }
        }
    }
    int q[maxn];
    int dist[maxn];
    int t;
    bool bfs(int s){
        int l=1,r=1;
        q[1]=s;
        memset(dist,-1,(n+1)*4);
        dist[s]=0;
        while(l<=r){
            int u=q[l++];
            for(int i=first[u];i<=num[u];i++){
                int v=e[i].to;
                if ((dist[v]!=-1) || (!e[i].cap))
                    continue;
                dist[v]=dist[u]+1;
                if (v==t)
                    return true;
                q[++r]=v;
            }
        }
        return dist[t]!=-1;
    }
    int dfs(int u,int flow){
        if (u==t)
            return flow;
        int ans=0;
        for(int& i=cur[u];i<=num[u];i++){
            int v=e[i].to;
            if (!e[i].cap || dist[v]!=dist[u]+1)
                continue;
            int t=dfs(v,min(flow,e[i].cap));
            if (t){
                e[i].cap-=t;
                e[e[i].rev].tot+=t;
                flow-=t;
                ans+=t;
                if (!flow)
                    return ans;
            }
        }
        return ans;
    }
    int MaxFlow(int s,int t){
        int ans=0;
        this->t=t;
        while(bfs(s)){
            do{
                memcpy(cur,first,(n+1)*4);
                int flow;
                while(flow=dfs(s,INF))
                    ans+=flow;
            }while(bfs(s));
            for(int i=1;i<=m;i++)
                e[i].cap+=e[i].tot,e[i].tot=0;
        }
        return ans;
    }
}DC;

int main(void)
{
    int N, M, S, T;
    while(~scanf("%d %d %d %d", &N, &M, &S, &T)){
        DC.init(N);
        while(M--){
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            DC.AddEdge(u, v, w);
        }
        DC.prepare();
        printf("%d", DC.MaxFlow(S, T));
    }
    return 0;
}

Dinic(这个快一点、点下标从1开始)

///这个是找到的别人的代码
///我见过的最快的最大流代码了
///但是我不知道原理，所以只能套一套这样子....
#include <bits/stdc++.h>

const int MAXN = 1e6 + 10;
const int INF = INT_MAX;

struct Node {
    int v, f, index;
    Node(int v, int f, int index) : v(v), f(f), index(index) {}
};

int n, m, s, t;
std::vector<Node> edge[MAXN];
std::vector<int> list[MAXN], height, count, que, excess;
typedef std::list<int> List;
std::vector<List::iterator> iter;
List dlist[MAXN];
int highest, highestActive;
typedef std::vector<Node>::iterator Iterator;

inline void init()
{
    for(int i=0; i<=n; i++)
        edge[i].clear();
}

inline void addEdge(const int u, const int v, const int f) {
    edge[u].push_back(Node(v, f, edge[v].size()));
    edge[v].push_back(Node(u, 0, edge[u].size() - 1));
}

inline void globalRelabel(int n, int t) {
    height.assign(n, n);
    height[t] = 0;
    count.assign(n, 0);
    que.clear();
    que.resize(n + 1);
    int qh = 0, qt = 0;
    for (que[qt++] = t; qh < qt;) {
        int u = que[qh++], h = height[u] + 1;
        for (Iterator p = edge[u].begin(); p != edge[u].end(); ++p) {
            if (height[p->v] == n && edge[p->v][p->index].f > 0) {
                count[height[p->v] = h]++;
                que[qt++] = p->v;
            }
        }
    }
    for (int i = 0; i <= n; i++) {
        list[i].clear();
        dlist[i].clear();
    }
    for (int u = 0; u < n; ++u) {
        if (height[u] < n) {
            iter[u] = dlist[height[u]].insert(dlist[height[u]].begin(), u);
            if (excess[u] > 0) list[height[u]].push_back(u);
        }
    }
    highest = (highestActive = height[que[qt - 1]]);
}

inline void push(int u, Node &e) {
    int v = e.v;
    int df = std::min(excess[u], e.f);
    e.f -= df;
    edge[v][e.index].f += df;
    excess[u] -= df;
    excess[v] += df;
    if (0 < excess[v] && excess[v] <= df) list[height[v]].push_back(v);
}

inline void discharge(int n, int u) {
    int nh = n;
    for (Iterator p = edge[u].begin(); p != edge[u].end(); ++p) {
        if (p->f > 0) {
            if (height[u] == height[p->v] + 1) {
                push(u, *p);
                if (excess[u] == 0) return;
            } else {
                nh = std::min(nh, height[p->v] + 1);
            }
        }
    }
    int h = height[u];
    if (count[h] == 1) {
        for (int i = h; i <= highest; i++) {
            for (List::iterator it = dlist[i].begin(); it != dlist[i].end();
                 ++it) {
                count[height[*it]]--;
                height[*it] = n;
            }
            dlist[i].clear();
        }
        highest = h - 1;
    } else {
        count[h]--;
        iter[u] = dlist[h].erase(iter[u]);
        height[u] = nh;
        if (nh == n) return;
        count[nh]++;
        iter[u] = dlist[nh].insert(dlist[nh].begin(), u);
        highest = std::max(highest, highestActive = nh);
        list[nh].push_back(u);
    }
}

inline int hlpp(int n, int s, int t) {
    if (s == t) return 0;
    highestActive = 0;
    highest = 0;
    height.assign(n, 0);
    height[s] = n;
    iter.resize(n);
    for (int i = 0; i < n; i++)
        if (i != s)
            iter[i] = dlist[height[i]].insert(dlist[height[i]].begin(), i);
    count.assign(n, 0);
    count[0] = n - 1;
    excess.assign(n, 0);
    excess[s] = INF;
    excess[t] = -INF;
    for (int i = 0; i < (int)edge[s].size(); i++) push(s, edge[s][i]);
    globalRelabel(n, t);
    for (int u /*, res = n*/; highestActive >= 0;) {
        if (list[highestActive].empty()) {
            highestActive--;
            continue;
        }
        u = list[highestActive].back();
        list[highestActive].pop_back();
        discharge(n, u);
        // if (--res == 0) globalRelabel(res = n, t);
    }
    return excess[t] + INF;
}

int main() {
    while(~scanf("%d %d %d %d", &n, &m, &s, &t)){
        init();
        for (int i = 0, u, v, f; i < m; i++) {
            scanf("%d %d %d", &u, &v, &f);
            addEdge(u, v, f);
        }
        printf("%d", hlpp(n + 1, s, t));///点是1~n范围的话，貌似要 n+1
    }
    return 0;
}

Highest Label Preflow Push(快到没人性)

最大流 && 最小费用最大流模板

相关推荐