首页 > 其他分享 >关于网络流的二三事

关于网络流的二三事

时间：2024-02-07 23:44:19浏览次数：21  
标签：ver cur idx int ne 网络 二三 ++ 关于

最大流

最大流模板-Dinic

#include <bits/stdc++.h>
using namespace std;
const int N = 10010,M = 2e5+10,INF = 0x3f3f3f3f;
int h[N],e[M],ne[M],f[M],idx;
int q[N],d[N],cur[N];
int n,m,S,T;
void add(int a,int b,int c)
{
    e[idx] = b,f[idx] = c,ne[idx] = h[a],h[a] = idx++;
    e[idx] = a,f[idx] = 0,ne[idx] = h[b],h[b] = idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    int tt = 0,hh = 0;
    q[0] = S,d[S] = 0,cur[S] = h[S];
    while(tt>=hh)
    {
        int t = q[hh++];
        
        for(int i = h[t];~i;i = ne[i])
        {
            int ver = e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if(ver==T) return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}
int find(int u,int limit)
{
    if(u==T) return limit;
    int flow = 0;
    for(int i = cur[u];~i&&flow<limit;i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if(d[ver]==d[u]+1&&f[i])
        {
            int t = find(ver,min(limit-flow,f[i]));
            if(!t) d[ver] = -1; 
            flow += t,f[i]-=t,f[i^1]+=t;
        }
        
    }
    return flow;
}
int dinic()
{
    int flow,r = 0;
    while(bfs())while(flow = find(S,INF)) r += flow;
    return r;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d%d%d",&n,&m,&S,&T);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    printf("%d\n",dinic());
    return 0;
}

上下界

无源汇上下界可行流

#include <bits/stdc++.h>
using namespace std;
const int N = 210,M = (10200+N)*2,INF = 0x3f3f3f3f;
int h[N],e[M],ne[M],f[M],l[M],idx;
int d[N],q[N],cur[N],A[N];
int n,m,S,T;
void add(int a,int b,int c,int d)
{
    e[idx] = b,f[idx] = d-c,l[idx] = c,ne[idx] = h[a],h[a] = idx++;
    e[idx] = a,f[idx] = 0,ne[idx] = h[b],h[b] = idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    int hh = 0,tt = 0;
    q[0] = S,d[S] = 0,cur[S] = h[S];
    
    while(hh<=tt)
    {
        int t = q[hh++];
        for(int i = h[t];~i;i = ne[i])
        {
            int ver = e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if(ver==T) return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}
int find(int u,int limit)
{
    if(u==T) return limit;
    int flow=  0;
    for(int i = cur[u];~i&&flow<limit;i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if(d[ver]==d[u]+1&&f[i])
        {
            int t = find(ver,min(f[i],limit-flow));
            if(!t) d[ver] = -1;
            flow += t,f[i] -=t,f[i^1]+=t;
        }
    }
    return flow;
}
int dinic()
{
    int r = 0,flow;
    while(bfs()) while(flow=find(S,INF)) r += flow;
    return r;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    S = 0,T = n+1;
    for(int i = 0;i<m;i++)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,c,d);
        A[a] -= c,A[b] += c;
    }
    int tot = 0;
    for(int i = 1;i<=n;i++)
    {
        if(A[i]>0) add(S,i,0,A[i]),tot += A[i];
        else if(A[i]<0) add(i,T,0,-A[i]);
    }
    
    if(dinic()!=tot) puts("NO");
    else
    {
        puts("YES");
        for(int i = 0;i<2*m;i+=2)
        {
            printf("%d\n",f[i^1]+l[i]);
        }
    }
    return 0;
}

有源汇上下界最大流

#include <bits/stdc++.h>
using namespace std;
const int N = 440,M = (10000+N) * 2,INF = 0x3f3f3f3f;
int h[N],e[M],f[M],ne[M],idx;
int d[N],cur[N],q[N],A[N];
int n,m,S,T;
void add(int a,int b,int c)
{
    e[idx] = b,f[idx] = c,ne[idx] = h[a],h[a] = idx++;
    e[idx] = a,f[idx] = 0,ne[idx] = h[b],h[b] = idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    int tt = 0,hh = 0;
    q[0] = S,d[S] = 0,cur[S] = h[S];
    while(tt>=hh)
    {
        int t = q[hh++];
        for(int i = h[t];~i;i= ne[i])
        {
            int ver = e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if(ver==T) return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}
int find(int u,int limit)
{
    if(u==T) return limit;
    int flow = 0;
    for(int i = cur[u];~i&&flow<limit;i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if(d[ver]==d[u]+1&&f[i])
        {
            int t = find(ver,min(limit-flow,f[i]));
            if(!t) d[ver] = -1;
            flow += t,f[i]-=t,f[i^1]+=t;
        }
    }
    return flow;
}
int dinic()
{
    int r = 0,flow;
    while(bfs()) while(flow = find(S,INF)) r += flow;
    return r;
}
int main()
{
    memset(h,-1,sizeof h);
    int s,t;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    S = 0,T = n+1;
    while(m--)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,d-c);
        A[b] += c,A[a] -=c;
    }
    int tot = 0;
    for(int i = 1;i<=n;i++)
    {
        if(A[i]>0) add(S,i,A[i]),tot+=A[i];
        else if(A[i]<0) add(i,T,-A[i]);
    }
    add(t,s,INF);
    if(dinic()<tot) puts("No Solution");
    else
    {
        S = s,T = t;
        int res = f[idx-1];
        f[idx-1] = f[idx-2] = 0;
        printf("%d\n",res+dinic());
    }
    return 0;
}

有源汇上下界最小流

#include <bits/stdc++.h>
using namespace std;
const int N = 500010,M = (N+125003) * 2,INF = 2147483647;
int h[N],e[M],ne[M],f[M],idx;
int q[N],cur[N],d[N],A[N];
int n,m,S,T;
void add(int a,int b,int c)
{
    e[idx] = b,f[idx] = c,ne[idx] = h[a],h[a] = idx++;
    e[idx] = a,f[idx] = 0,ne[idx] = h[b],h[b] = idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    int tt = 0,hh = 0;
    q[0] = S,d[S] = 0,cur[S] = h[S];
    while(hh<=tt)
    {
        int t = q[hh++];
        for(int i = h[t];~i;i = ne[i])
        {
            int ver = e[i];
            if(d[ver]==-1&&f[i])
            {
                cur[ver] = h[ver];
                d[ver] = d[t] + 1;
                if(ver==T) return true;
                q[++tt] =  ver;
            }
        }
    }
    return false;
}
int find(int u,int limit)
{
    if(u==T) return limit;
    int flow = 0;
    for(int i = cur[u];~i&&flow<limit;i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if(d[ver]==d[u]+1&&f[i])
        {
            int t = find(ver,min(limit-flow,f[i]));
            if(!t) d[ver] = -1;
            f[i] -= t,flow += t,f[i^1]+=t;
        }
    }
    return flow;
}
int dinic()
{
    int r = 0,flow;
    while(bfs()) while(flow=find(S,INF)) r += flow;
    return r;
}
int main()
{
    memset(h,-1,sizeof h);
    int s,t;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    S = 0,T = n+1;
    while(m--)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,d-c);
        A[a] -=c,A[b] += c;
    }
    
    int tot = 0;
    for(int i = 1;i<=n;i++)
    {
        if(A[i]>0) add(S,i,A[i]),tot += A[i];
        else if(A[i]<0) add(i,T,-A[i]);
    }
    
    add(t,s,INF);
    if(dinic()!=tot) puts("No Solution");
    else
    {
        int res = f[idx-1];
        S = t,T = s;
        f[idx-1] = f[idx-2] = 0;
        printf("%d\n",res-dinic());
    }
    return 0;
}

最大流求解二分图匹配

思路大致是把所有匹配点分成两部分，S（源点）向左边的匹配点（可以自己定义），连一条容量为1的边，表示这个点有一个人，左边的匹配点向右边的可匹配点连一条容量是1的边（表示左边的人可以跟右边的人完成一次匹配），右边的匹配点向汇点T连一条容量是1的边

洛谷-飞行员匹配问题

image

#include <bits/stdc++.h>
using namespace std;
const int N = 110,M = 10010,INF = 0x3f3f3f3f;
int h[N],e[M],ne[M],f[M],idx;
int q[N],d[N],cur[N];
int n,m,S,T;
void add(int a,int b,int c)
{
    e[idx] = b,f[idx] = c,ne[idx] = h[a],h[a] = idx++;
    e[idx] = a,f[idx] = 0,ne[idx] = h[b],h[b] = idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    int tt = 0,hh = 0;
    q[0] = S,d[S] = 0,cur[S] = h[S];
    
    while(tt>=hh)
    {
        int t = q[hh++];
        for(int i = h[t];~i;i = ne[i])
        {
            int ver = e[i];
            
            if(f[i]&&d[ver]==-1)
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if(ver==T) return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}
int find(int u,int limit)
{
    if(u==T) return limit;
    int flow = 0;
    for(int i = cur[u];~i&&flow<limit;i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if(f[i]&&d[ver]==d[u]+1)
        {
            int t = find(ver,min(limit-flow,f[i]));
            if(!t) d[ver] = -1;
            flow += t,f[i] -= t,f[i^1]+=t;
        }
    }
    return flow;
}
int dinic()
{
    int r = 0,flow;
    while(bfs())while(flow = find(S,INF)) r += flow;
    return r;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&m,&n);
    S = 0,T = n+1;
    for(int i = 1;i<=m;i++) add(S,i,1);
    for(int i = m+1;i<=n;i++) add(i,T,1);
    
    int a,b;
    while(scanf("%d%d",&a,&b),a!=-1) add(a,b,1); 
    printf("%d\n",dinic());
    
    for(int i = 0;i<idx;i+=2)
    {
        if(e[i]>m&&e[i]<=n&&!f[i])
        {
            printf("%d %d\n",e[i^1],e[i]);
        }
    }
    return 0;
}

洛谷-圆桌问题

#include <bits/stdc++.h>
using namespace std;
const int N = 500,M = N*N,INF = 1e9;
int h[N],e[M],f[M],ne[M],idx;
int cur[N],q[N],d[N];
int n,m,S,T;
int r[N],des[N];
void add(int a,int b,int c)
{
    e[idx] = b,f[idx] = c,ne[idx] = h[a],h[a] = idx++;
    e[idx] = a,f[idx] = 0,ne[idx] = h[b],h[b] = idx++;
}
bool bfs()
{
    int tt = 0,hh = 0;
    memset(d,-1,sizeof d);
    q[0] = S,d[S] = 0,cur[S] = h[S];
    while(tt>=hh)
    {
        int t = q[hh++];
        for(int i = h[t];~i;i = ne[i])
        {
            int ver = e[i];
            if(d[ver] == -1&& f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if(ver==T) return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}
int find(int u,int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u];~i&&flow<limit;i = ne[i])
    {
        int ver = e[i];
        if(d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver,min(limit-flow,f[i]));
            if(!t) d[ver] = -1;
            f[i] -= t,f[i^1] += t,flow += t;
        }
    }
    return flow;
}
int dinic()
{
    int r = 0,flow;
    while(bfs()) while(flow = find(S,INF)) r += flow;
    return r;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&m,&n);
    S = 0,T = n+m+1;
    int tot = 0;
    for(int i = 1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        add(S,i,x);
        tot += x;
    }
    for(int i = 1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        add(i+m,T,x);
    }

    for(int i = 1;i<=m;i++)for(int j = 1;j<=n;j++) add(i,j+m,1);
    if(tot == dinic())
    {
        puts("1");
        for(int i = 1;i<=m;i++)
        {
            for(int j = h[i];~j;j = ne[j])
            {
                if(e[j]>m&&e[j]<=m+n&&!f[j])
                {
                    printf("%d ",e[j]-m);
                }
            }
            puts("");
        }
    }
    else puts("0");
    return 0;
}

标签：ver,cur,idx,int,ne,网络,二三,++,关于
From： https://www.cnblogs.com/howardsblog/p/18011497

相关文章

  • Vmware虚拟机突然连不上网络(WiFi)解决办法
    虚拟机Vmware突然连不了网络的解决思路虚拟机常用的三种网络连接方式1、桥接：就是把虚拟机通过VMnet0桥接到主机的本地连接。在桥接模式下，使用VMware创建的虚拟机就像是你买了一台新主机接到了局域网的交换机或者路由器上。它可以配置IP地址、子网掩码和其它的TCP/IP信息，......
  • 线性规划和网络流的单纯形法
    线性规划线性规划问题求\[\max\sum_{i=1}^nc_jx_j\\\text{s.t.:}\\\sum_{t=1}^na_{it}x_t\leb_i,i\in\Z\cap[1,m_1]\\\sum_{t=1}^na_{it}x_t=b_i,i\in\Z\cap(m_1,m_1+m_2]\\\sum_{t=1}^na_{it}x_t\geb_i,i\in(m_1+m_2,m_1+m_2+m_3]\\x_......
  • 【AutoML】AutoKeras 进行 RNN 循环神经网络训练
    由于最近这些天都在人工审查之前的哪些问答数据，所以迟迟都没有更新AutoKeras的训练结果。现在那部分数据都已经整理好了，20w+的数据最后能够使用的高质量数据只剩下2k+。这2k+的数据已经经过数据校验并且对部分问题的提问方式和答案内容进行了不改变原意的重构，相信用这部分数......
  • 神经网络包nn和优化器optm
    torch.nn是专门为神经网络设计的模块化接口。nn构建于Autograd之上，可用来定义和运行神经网络。这里我们主要介绍几个一些常用的类除了nn别名以外，我们还引用了nn.functional，这个包中包含了神经网络中使用的一些常用函数，这些函数的特点是，不具有可学习的参数(如ReLU，pool，DropOut等)......
  • 网络流
    当学习笔记用，持续更新。写给自己看的，图有点少。如果有人真想通过这篇博客学网络流的话也不是不行……因为更新极慢无比，所以这篇博客里的各份代码码风可能会出现巨大的差别。关于学习途径显然有无数人在自学网络流的时候因为网上大部分题解的姿势都过于抽象而被劝退，所以提一下......
  • 北极网络
    不知道这道题目跟最小\(k\)度生成树有什么关系，到时候可以想一下不要一看到特殊点就想虚点，这道题目我们这么建模假设我们的\(D\)已经定了，我们把边权小于等于\(D\)的全部加入，那么图就会形成一个若干个连通块显然\(D\)越大连通块个数越少这里当然启示我们用二分，然而也有更简单的......
  • 【面试突击】网络通信面试实战
    网络通信面试实战Socket工作原理Socket是应用层与TCP/IP协议族通信的中间软件抽象层，它是一组接口，其实就是一个门面模式，将底层复杂的通信操作给封装起来对外提供接口。简单来说就是Socket把TPC/IP协议给封装了起来，我们的程序进行网络通信都是通过Socket来完成的！也就是说当......
  • 华为配置访客接入WLAN网络示例（MAC优先的Portal认证）
    配置访客接入WLAN网络示例（MAC优先的Portal认证）组网图形图1 配置WLANMAC优先的Portal认证示例组网图业务需求组网需求数据规划配置思路配置注意事项操作步骤配置文件业务需求某企业为了提高WLAN网络的安全性，采用MAC优先的外置Portal认证方式，实现对用户的接入控制。组网需求AC组网......
  • 深度学习网络的感受野与卷积核
    https://www.bilibili.com/read/cv27451493/?jump_opus=1https://zhuanlan.zhihu.com/p/484653541?utm_id=0一般认为，网络越深，卷积核越大，感受野也就越大。同时，也会丢失一定的小尺度捕捉能力。在《Residualnetworksbehavelikeensemblesofrelativelyshallownetworks》中，说......
  • 建站之关于CP网站SSC搭建BC平台建站建议和运营优化分享
    关于搭建BC平台建站建议和运营优化分享，我可以在一定程度上提供一些信息和经验。一、关于搭建BC平台建站建议：确定网站目标和受众群体：在开始构建网站之前，需要明确网站的定位和目标受众群体。这将有助于确保网站内容符合受众需求，提高转化率。选择合适的开发语言和技术框架：根据网站......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99