每日一题6.5

XinyuLin

图论-网络流

模版，蓝名---P3376 【模板】网络最大流 - 洛谷
例题，紫名P2754 [CTSC1999] 家园 / 星际转移问题 - 洛谷
相关算法
Ford-Fulkerson算法
Edmond-Karp算法
Dinic算法
这里再提一下最大流最小割定理。所谓割，就是从网络中选择一些边，使得去掉这些边后，剩下两个不连通的分别包含源点和汇点的点集。割的大小是这些边的容量之和。在所有可行的割中，最小的割称为最小割。

这个神奇的定理只有短短几个字：最大流等于最小割。

495684945

EK算法,然而并不能解决模板题  O(n*m^2)

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;

void solve(){
        int n,m,s,t,idx=0;
        cin>>n>>m>>s>>t;
        vector<int>h(n+10,-1),ne(2*m+10),e(2*m+10),f(2*m+10);
        auto add=[&](int a,int b,int c){
                e[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++;
        };
        for(int i=1,a,b,c;i<=m;i++){
                cin>>a>>b>>c;
                add(a,b,c);
                add(b,a,0);
        }
        vector<int>pre(n+10),mf(n+10);
        auto bfs=[&](){
                fill(mf.begin(),mf.end(),0);
                mf[s]=1e18;
                queue<int>q;
                q.push(s);
                while(q.size()){
                        auto u=q.front();
                        q.pop();
                        for(int i=h[u];i!=-1;i=ne[i]){
                                int x=e[i],y=f[i];
                                if(mf[x]==0&&y>0){
                                        mf[x]=min(mf[u],y);
                                        pre[x]=i;
                                        q.push(x);
                                        if(x==t)return true;
                                }
                        }
                }
                return false;
        };
        int ans=0;
        while(bfs()){
                int v=t;
                while(v!=s){
                        int i=pre[v];
                        f[i]-=mf[t];
                        f[i^1]+=mf[t];
                        v=e[i^1];
                }
                ans+=mf[t];
        }
        cout<<ans<<endl;
}

signed main(){
        int t=1;ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//        cin>>t;
        while(t--)solve();
        return 0;
}

Fengyj

Dinic算法，时间复杂度O(n^2 *m) 可通过

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

template <typename T>
struct Flow_
{
    const int n;
    const T inf = numeric_limits<T>::max();
    struct Edge
    {
        int to;
        T w;
        Edge(int to, T w) : to(to), w(w) {}
    };
    vector<Edge> ver;
    vector<vector<int>> h;
    vector<int> cur, d;

    Flow_(int n) : n(n + 1), h(n + 1) {}
    void add(int u, int v, T c)
    {
        h[u].push_back(ver.size());
        ver.emplace_back(v, c);
        h[v].push_back(ver.size());
        ver.emplace_back(u, 0);
    }
    bool bfs(int s, int t)
    {
        d.assign(n, -1);
        d[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty())
        {
            auto x = q.front();
            q.pop();
            for (auto it : h[x])
            {
                auto [y, w] = ver[it];
                if (w && d[y] == -1)
                {
                    d[y] = d[x] + 1;
                    if (y == t)
                        return true;
                    q.push(y);
                }
            }
        }
        return false;
    }
    T dfs(int u, int t, T f)
    {
        if (u == t)
            return f;
        auto r = f;
        for (int &i = cur[u]; i < h[u].size(); i++)
        {
            auto j = h[u][i];
            auto &[v, c] = ver[j];
            auto &[u, rc] = ver[j ^ 1];
            if (c && d[v] == d[u] + 1)
            {
                auto a = dfs(v, t, std::min(r, c));
                c -= a;
                rc += a;
                r -= a;
                if (!r)
                    return f;
            }
        }
        return f - r;
    }
    T work(int s, int t)
    {
        T ans = 0;
        while (bfs(s, t))
        {
            cur.assign(n, 0);
            ans += dfs(s, t, inf);
        }
        return ans;
    }
};
using Flow = Flow_<i64>;
void solve(){
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    Flow flow(n);
    for (int i = 0; i < m;i++){
        int u, v, w;
        cin >> u >> v >> w;
        flow.add(u, v, w);
    }
    i64 ans = flow.work(s,t);
    cout << ans << '\n';
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}