每日一题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;
}

495684945

Dinic算法

[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(m*2+10),e(m*2+10),c(m*2+10),h2(n+10);
	auto add=[&](int a,int b,int c2){
		e[idx]=b,ne[idx]=h[a],c[idx]=c2,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>d(n+10);
	auto bfs=[&]()->bool{
		fill(d.begin(),d.end(),0);
		queue<int>q;
		d[s]=1;
		q.push(s);
		while(q.size()){
			auto t1=q.front();
			q.pop();
			for(int i=h[t1];i!=-1;i=ne[i]){
				if(d[e[i]]!=0||c[i]==0)continue;
				q.push(e[i]);
				d[e[i]]=d[t1]+1;
				if(e[i]==t)return true;
			}
		}
		return false;
	};
	auto dfs=[&](auto dfs,int u,int mf)->int{
		if(u==t)return mf;
		int sum=0;
		for(int i=h2[u];i!=-1;i=ne[i]){
			h2[u]=i;//记录一下从u最后到的一次是哪里
			//如果mf>=c[i] 这条边就已经用完了,另一条路径还到u这就直接去h2[u],前面u到其他走过的肯定走满了
			//如果mf<c[i] 这个边没用完,如果h2记录后面的就错了,但是边没用完,mf用完了，走if(mf==0)break; 所以这两行要不一起在,要不一起不在,不然错
			if(d[e[i]]==d[u]+1 && c[i]){
				int f=dfs(dfs,e[i],min(mf,c[i]));
				c[i]-=f;
				c[i^1]+=f;
				sum+=f;
				mf-=f;
				if(mf==0)break;//流量已经用完了后面都给不了
			}
		}
		if(sum==0)d[u]=0;//u节点跑完所有可能能到的点都还是0,证明一个都不能到,直接毁掉d[u]不让其他路径浪费时间了
		return sum;
	};
	int ans=0;
	while(bfs()){
		h2=h;
		ans+=dfs(dfs,s,1e18);
	}
	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;
}