chail's Blog
博客 分类 标签
chail's Blog

目录

目录

费用流&左偏树可并堆

 收录于  类别 算法足迹
     约 2684 字   预计阅读 12 分钟 

费用流&左偏树可并堆

很久没有写新算法学习的文章了，随着水平上升，我接触的题目越来越难，也是时候学习一些高级的算法与数据结构了。今天我们来学习费用流与左偏树可并堆。

给出一个包含 n 个点和 m 条边的有向图（下面称其为网络） G=(V,E)，该网络上所有点分别编号为 1∼n，所有边分别编号为 1∼m，其中该网络的源点为 s，汇点为 t，网络上的每条边 (u,v) 都有一个流量限制 w(u,v) 和单位流量的费用 c(u,v)。

你需要给每条边 (u,v) 确定一个流量 f(u,v)，要求：

  1. 0≤f(u,v)≤w(u,v)（每条边的流量不超过其流量限制）；
  2. $\forall p \in {V \setminus {s,t}}，，\sum_{(i,p) \in E}f(i,p)=\sum_{(p,i)\in E}f(p,i)$（除了源点和汇点外，其他各点流入的流量和流出的流量相等）；
  3. ∑(s,i)∈Ef(s,i)=∑(i,t)∈Ef(i,t)（源点流出的流量等于汇点流入的流量）。

定义网络 G 的流量 F(G)=∑(s,i)∈Ef(s,i)，网络 G 的费用 C(G)=∑(i,j)∈Ef(i,j)×c(i,j)。

你需要求出该网络的最小费用最大流，即在 F(G) 最大的前提下，使 C(G) 最小。

输入第一行包含四个整数 n,m,s,t，分别代表该网络的点数 n，网络的边数 m，源点编号 s，汇点编号 t。

接下来 m 行，每行四个整数 ui,vi,wi,ci，分别代表第 i 条边的起点，终点，流量限制，单位流量费用。

输出两个整数，分别为该网络的最大流 F(G)，以及在 F(G) 最大的前提下，该网络的最小费用 C(G)。

费用流问题是网络流的扩展，而网络流有两种常见算法：EK与Dinic。

同样是寻找最大流，费用流要求我们花费最小。在网络流中我们寻找最大流时，需要不断地寻找增广路，费用流既然也要找最大流，当然也逃不开这一点。那怎么保证费用最小呢。

在一张图上找到费用最小的路径，这是我们从前就解决过的问题：最短路。如果最短路同时也是增广路，那无疑选择这条路一定最优的。

上述算法叫做SSP（Successive Shortest Path）连续最短路：每次沿着当前残留网络中费用最短路增广单位流量，直到无法增广为止。

在EK算法中，我们通过BFS寻找所有的增广路实现最大流，而现在我们要做的是寻找所有的最短增广路，只不过是多了一个最短路。单源最短路算法常用的有Dijkstra和SPFA，由于我们要像网络流一样构建反悔边所以一定会有负权边。Dijkstra想要处理这种负权边需要加上一个势能处理（没学qwq），而SPFA天然支持处理负权边，所以这里用SPFA。

通过SPFA我们同时寻找增广路和最短路，直到找不到这样的路，就找到了答案。

#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 5e3+5;
constexpr int maxm = 5e4+5;
int n,m,s,t;
struct e {
    int t,w,c;
    int rev;
};
vector<e> g[maxn];
void addEdge(int u,int v,int w,int c) {
    g[u].push_back({v, w, c, (int)g[v].size()});
    g[v].push_back({u, 0, -c, (int)g[u].size()-1});
}
array<int, maxn> pre_v, pree,dist;
array<bool, maxn> u;
bool spfa() {
    dist.fill(1e9);
    u.fill(false);
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    u[s] = true;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        u[v] = false;
        for (int i = 0; i < g[v].size(); i++) {
            e& ei = g[v][i];
            if (ei.w && dist[v]+ei.c < dist[ei.t]) {
                dist[ei.t] = dist[v]+ei.c;
                pre_v[ei.t] = v;
                pree[ei.t] = i;
                if (!u[ei.t]) {
                    u[ei.t] = true;
                    q.push(ei.t);
                }
            }
        }
    }
    return dist[t]<1e9;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> s >> t;
    for (int i=1;i<=m;++i) {
        int ui,v,w,c;
        cin >> ui >> v >> w >> c;
        addEdge(ui,v,w,c);
    }
    int maxflow=0;
    int mincost = 0;
    while (spfa()) {
        int flow = 0x3f3f3f;
        for (int v=t;v!=s;v = pre_v[v]) {
            int i = pree[v];
            flow = min(flow, g[pre_v[v]][i].w);
        }
        maxflow += flow;
        mincost += flow*dist[t];
        for (int v=t;v!=s;v = pre_v[v]) {
            int i = pree[v];
            g[pre_v[v]][i].w -= flow;
            int reve = g[pre_v[v]][i].rev;
            g[v][reve].w += flow;
        }
    }
    cout << maxflow << " " << mincost << endl;
    return 0;
}

通过SPFA一条又一条的寻找最短增广路无疑是低效的，而Dinic算法通过DFS一次寻找多条增广路，可以大幅提升速度，尤其是在稠密图。

同样的思路，我们用SPFA寻找最短路并构建分层图，接着用DFS在分层图上寻找增广路。这样便实现了高效处理。

#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 5e3+5;
constexpr int maxm = 5e4+5;
int n,m,s,t;
struct e {
    int t,w,c;
    int rev;
};
vector<e> g[maxn];
array<int,maxn> dist,cur;
array<bool, maxn> vis;
void addEdge(int u,int v, int w, int c) {
    g[u].push_back({v,w,c, (int)g[v].size()});
    g[v].push_back({u,0,-c, (int)g[u].size()-1});
}
bool spfa() {
    dist.fill(1e9);
    array<bool,maxn> inq{};
    queue<int> q;
    dist[s] = 0;
    inq[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (e& ei:g[u]) {
            if (ei.w && dist[u]+ei.c < dist[ei.t]) {
                dist[ei.t] = dist[u]+ei.c;
                if (!inq[ei.t]) {
                    inq[ei.t] = true;
                    q.push(ei.t);
                }
            }
        }
    }
    return dist[t] < 1e9;
}
int dfs(int u, int lim) {
    if (u==t) return lim;
    vis[u] = true;
    int res = 0;
    int k;
    for (int i=cur[u];i<g[u].size() && lim;++i) {
        cur[u] = i;
        e& ei = g[u][i];
        if (ei.w && dist[u]+ei.c==dist[ei.t] && !vis[ei.t]) {
            k = dfs(ei.t, min(lim, ei.w));
            if (!k) {
                dist[ei.t] = -1;
                continue;
            }
            ei.w-=k;
            g[ei.t][ei.rev].w+=k;
            res += k;
            lim -= k;
        }
    }
    vis[u] = false;
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> s >> t;
    for (int i=1;i<=m;++i) {
        int u,v,w,c;
        cin >> u >> v >> w >> c;
        addEdge(u,v,w,c);
    }
    int maxflow=0;
    int mincost=0;
    while (spfa()) {
        cur.fill(0);
        while (int flow=dfs(s, 0x3f3f3f)) {
            maxflow += flow;
            mincost += flow*dist[t];
        }
    }
    cout << maxflow << " " << mincost << endl;
    return 0;
}

学完网络流，费用流还是很好理解的。

接着来学习一个重量级数据结构：左偏树。

左偏树是一种二叉树构成的堆，并且是可并堆。可并堆就是可以合并的堆。个人觉得十分巧妙。

模板题：

如题，一开始有 $n$ 个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：

  1. 1 x y：将第 $x$ 个数和第 $y$ 个数所在的小根堆合并（若第 $x$ 或第 $y$ 个数已经被删除或第 $x$ 和第 $y$ 个数在同一个堆内，则无视此操作）。

  2. 2 x：输出第 $x$ 个数所在的堆最小数，并将这个最小数删除（若有多个最小数，优先删除先输入的；若第 $x$ 个数已经被删除，则输出 $-1$ 并无视删除操作）。

第一行包含两个正整数 $n, m$，分别表示一开始小根堆的个数和接下来操作的个数。

第二行包含 $n$ 个正整数，其中第 $i$ 个正整数表示第 $i$ 个小根堆初始时包含且仅包含的数。

接下来 $m$ 行每行 $2$ 个或 $3$ 个正整数，表示一条操作，格式如下：

操作 $1$：1 x y

操作 $2$：2 x

输出包含若干行整数，分别依次对应每一个操作 $2$ 所得的结果。

左偏树引入Npl（Null Path Length）值：节点到最近的空子节点的距离，空节点的 $Npl$为 $-1$。

而左偏树的约束就是，任意节点的左孩子$Npl$ $>=$ 右孩子 $Npl$。也就是任意节点左子树的最深深度不会小于右子树最深深度。这样就保证了如果沿着右孩子走，一定是到达空子节点的最短路径。右路径的长度 $<=log_2n$。

左偏树的核心操作是合并，例如合并根为 $x$ 和 $y$ 的两个左偏树，如果 $Npl_x > Nply$，交换 $x$ 和 $y$ 保证 $x$ 的 $Nlp$ 不大于 $y$，然后递归合并 $x$ 的右子树与 $y$。因为左偏树的性质，这个合并路径一定是最短的，保证了算法速度更快。一旦 $x$ 或 $y$ 为空，便返回非空的一方，递归回溯。

回溯时需要更新新节点的 $Npl$，同时需要维护左偏性，也就是如果左子树更“小”就和右子树交换。

这样我们就通过 $O(logn)$ 的复杂度实现了合并的操作。利用左偏性来实现高效合并，是不是很巧妙呢，实在令人拍案叫绝。

这个堆的删除则是通过合并根节点的左右子树实现。

#include<bits/stdc++.h>
using namespace std;
constexpr int maxn = 1e5+5;
int n,m;
array<int,maxn> lc,rc,dist,rt;
bool tf[maxn];
struct node {
    int id,v;
    bool operator < (const node &p) const {
        return v==p.v ? id<p.id : v<p.v;
    }
};
node v[maxn];
int find(int x) {
    if (x==rt[x]) return x;
    return rt[x] = find(rt[x]);
}
int merge(int x, int y) {
    if (!x || !y) return x+y;
    if (v[y]<v[x]) swap(x,y);
    rc[x] = merge(rc[x], y);
    if (dist[lc[x]]<dist[rc[x]]) swap(lc[x],rc[x]);
    dist[x] = dist[rc[x]]+1;
    return x;
}
int main() {
    dist[0] = -1;
    cin >> n >> m;
    for (int i=1;i<=n;++i) {
        int vi;
        cin >> vi;
        rt[i]=i;
        v[i].id=i;
        v[i].v=vi;
    }
    while (m--) {
        int op;
        cin >> op;
        if (op==1) {
            int x,y;
            cin >> x >> y;
            if (tf[x] || tf[y]) continue;
            x = find(x);
            y = find(y);
            if (x!=y) rt[x] = rt[y] = merge(x,y);
        }
        else {
            int x;
            cin >> x;
            if (tf[x]) {
                cout << "-1\n";
                continue;
            }
            x = find(x);
            cout << v[x].v << "\n";
            tf[x] = true;
            rt[lc[x]] = rt[rc[x]] = rt[x]=merge(lc[x],rc[x]);
            lc[x] = rc[x] = dist[x] = 0;
        }
    }
    return 0;
}
更新于 2026-08-10
 | 主页