首页 > 其他分享 >网络流阶段性总结

网络流阶段性总结

时间：2023-07-16 20:14:26浏览次数：48  
标签：总结 阶段性 ver int flow 网络 edge limit return

网络流，一种建图的艺术

显然我没有那种艺术细胞（悲

$\ $

最大流

dinic+当前弧优化

$\ $

#include<bits/stdc++.h>
using namespace std;
const int N=4e4+10,M=1e5+10,inf=1e9;
int n1,n2,n3,m1,m2,s,t;
int cur[N],vis[N],dis[N];
int ver[M<<1],head[N],tot=1,Next[M<<1],edge[M<<1];
void add(int x,int y,int z){
    ver[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
    edge[tot]=z;
}
bool bfs(){
    for(int i=1;i<=t;i++)dis[i]=0,cur[i]=head[i];
    queue<int>q;
    dis[s]=1;
    q.push(s);
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(!dis[y]&&edge[i]){
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
    return (dis[t]!=0);
}
int dinic(int x,int limit){
    if(x==t||!limit)return limit;
    int flow=0,f;
    for(int &i=cur[x];i;i=Next[i]){
        int y=ver[i];
        if(dis[y]==dis[x]+1&&(f=dinic(y,min(limit,edge[i])))){
            flow+=f,limit-=f;
            edge[i]-=f,edge[i^1]+=f;
            if(!limit)break;
        }
    }
    return flow;
}
int main()
{
    scanf("%d%d%d",&n1,&n2,&n3);
    s=n1+n1+n2+n3+1,t=n1+n1+n2+n3+2;
    scanf("%d",&m1);
    for(int i=1,x,y;i<=m1;i++){
        scanf("%d%d",&x,&y);
        add(x+n2,y,0),add(y,x+n2,1);
    }
    scanf("%d",&m2);
    for(int i=1,x,y;i<=m2;i++){
        scanf("%d%d",&x,&y);
        add(x+n2+n1,y+n1+n2+n1,1),add(y+n1+n2+n1,x+n2+n1,0);
    }
    for(int i=1;i<=n1;i++){
        add(i+n2,i+n2+n1,1),add(i+n2+n1,i+n2,0);
    }
    for(int i=1;i<=n2;i++){
        add(s,i,1),add(i,s,0);
    }
    for(int i=1;i<=n3;i++){
        add(i+n1+n2+n1,t,1),add(t,i+n1+n2+n1,0);
    }
    int flow=0;
    while(bfs()){
        flow+=dinic(s,inf);
    }
    printf("%d\n",flow);
    return 0;
}

$\ $

  • P1345 [USACO5.4] 奶牛的电信Telecowmunication
    拆成出边点和入边点，控制点的流量为 \(1\)
    路径会通过相连的信息建立联系，路径上的每个点都先走到入点，经过流量为 \(1\) 的控制边，再走到出点，保证了流量合法
#include<bits/stdc++.h>
using namespace std;
const int N=410,M=2010,inf=1e9;
int n,m,c1,c2;
int ver[M<<1],head[N],tot=1,Next[M<<1],edge[M<<1];
int cur[N],d[N];
void add(int x,int y,int z){
    ver[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
    edge[tot]=z;
}
bool bfs(){
    for(int i=1;i<=n*2;i++)cur[i]=head[i],d[i]=0;
    queue<int>q;
    d[c1]=1;
    q.push(c1);
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(!d[y]&&edge[i]){
                d[y]=d[x]+1;
                q.push(y);
            }
        }
    }
    return (d[c2]!=0);
}
int dinic(int x,int limit){
    if(x==c2||!limit)return limit;
    int flow=0,f;
    for(int &i=cur[x];i;i=Next[i]){
        int y=ver[i];
        if(d[y]==d[x]+1&&(f=dinic(y,min(limit,edge[i])))){
            flow+=f,limit-=f;
            edge[i]-=f,edge[i^1]+=f;
            if(!limit)break;
        }
    }
    return flow;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&c1,&c2);
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x+n,y,inf),add(y,x+n,0);
        add(y+n,x,inf),add(x,y+n,0);
    }
    for(int i=1;i<=n;i++){
        if(i!=c1&&i!=c2)add(i,i+n,1),add(i+n,i,0);
        else add(i,i+n,inf),add(i+n,i,0);
    }
    int flow=0;
    while(bfs()){
        flow+=dinic(c1,inf);
    }
    printf("%d\n",flow);
    return 0;
}

$\ $

最小割

最后的网络中，与S相连的相当于选进 \(S\) 集合，与 \(T\) 相连的则是选进 \(T\) 集合
最小割是分成两个集合的最小割边代价

$\ $

  • P1361 小M的作物
    把每个植物组合作为两个新点。\(S\) 向新点\(1\)连流量 \(c_{i,1}\) 的边，新点 \(2\) 向 \(T\) 连流量 \(c_{i,2}\) 的边，表示不选进这两个集合的话分别少收获多少贡献。
    新点 \(1\) 向相应的作物点连不会被割掉的流量为 \(inf\) 的边，同样地，作物向新点 \(2\) 连不会被割掉的边。
    如果某个组合连向 \(S\) 的边没有被割掉，那么组合中所有作物连向 \(T\) 的点都被割掉了。反之同理。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10,M=3e6+10;
const ll inf=1e18;
int n,s,t,m,cnt,cur[N],d[N];
ll a[N],b[N],edge[M],sum;
int ver[M],head[N],tot=1,Next[M];
void add(int x,int y,ll z){
    ver[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
    edge[tot]=z;
}
bool bfs(){
    for(int i=1;i<=cnt;i++)d[i]=0,cur[i]=head[i];
    d[s]=1;
    queue<int>q;
    q.push(s);
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(!d[y]&&edge[i]){
                d[y]=d[x]+1;
                q.push(y);
            }
        }
    }
    return (d[t]!=0);
}
ll dinic(int x,ll limit){
    if(x==t||!limit)return limit;
    ll flow=0,f;
    for(int &i=cur[x];i;i=Next[i]){
        int y=ver[i];
        if(d[y]==d[x]+1&&(f=dinic(y,min(limit,edge[i])))){
            flow+=f,limit-=f;
            edge[i]-=f,edge[i^1]+=f;
            if(!limit)break;
        }
    }
    return flow;
}
int main()
{
    scanf("%d",&n);
    s=n+1,t=cnt=n+2;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        add(s,i,a[i]),add(i,s,0);
        sum+=a[i];
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
        add(i,t,b[i]),add(t,i,0);
        sum+=b[i];
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int k,c1,c2;
        scanf("%d%d%d",&k,&c1,&c2);
        sum+=c1+c2;
        add(s,cnt+1,c1),add(cnt+1,s,0);
        add(cnt+2,t,c2),add(t,cnt+2,0);
        for(int j=1,x;j<=k;j++){
            scanf("%d",&x);
            add(cnt+1,x,inf),add(x,cnt+1,0);
            add(x,cnt+2,inf),add(cnt+2,x,0);
        }
        cnt+=2;
    }
    ll flow=0;
    while(bfs()){
        flow+=dinic(s,inf);
    }
    printf("%lld\n",sum-flow);
    return 0;
}

$\ $

  • P2057 [SHOI2007] 善意的投票 / [JLOI2010] 冠军调查
    最小割连边的板子模型之一
    \(S\) 投 \(0\),\(T\) 投 \(1\),每个人向自己的意愿连边，朋友之间连流量为 \(1\) 的边。
    要么割意愿边，满足朋友投了同一种票；要么割朋友边，满足自己的意愿但发生冲突。
#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=2e5+10,inf=1e9;
int n,m,s,t,ans,cnt,cur[N],d[N];
int ver[M<<1],head[N],tot=1,Next[M<<1],edge[M<<1];
void add(int x,int y,int z){
    ver[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
    edge[tot]=z;
    ver[++tot]=x;
    Next[tot]=head[y];
    head[y]=tot;
    edge[tot]=z;
}
bool bfs(){
    for(int i=1;i<=cnt;i++)cur[i]=head[i],d[i]=0;
    d[s]=1;
    queue<int>q;
    q.push(s);
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(!d[y]&&edge[i]){
                d[y]=d[x]+1;
                q.push(y);
            }
        }
    }
    return (d[t]!=0);
}
int dinic(int x,int limit){
    if(x==t||!limit)return limit;
    int flow=0,f;
    for(int &i=cur[x];i;i=Next[i]){
        int y=ver[i];
        if(d[y]==d[x]+1&&(f=dinic(y,min(limit,edge[i])))){
            flow+=f,limit-=f;
            edge[i]-=f,edge[i^1]+=f;
            if(!limit)break;
        }
    }
    return flow;
}
int main()
{
    scanf("%d%d",&n,&m);
    s=n+1,t=cnt=n+2;
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        if(x==1)add(i,t,1);
        else add(s,i,1);
    }
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y,1),add(y,x,1);
    }
    int flow=0;
    while(bfs()){
        flow+=dinic(s,inf);
    }
    printf("%d\n",flow);
    return 0;
}

$\ $

  • P2762 太空飞行计划问题
    源点向实验连边，实验向对应仪器连边，仪器向汇点连边，初始统计所有实验的价值
    割掉实验表示不选这场实验，割掉仪器表示付出仪器的代价完成实验
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
const ll inf=1e18;
int m,n,c[N],s,t,d[N],cur[N],p[N],a[N],cnt,vis[N];
int ver[N<<1],head[N],tot=1,Next[N<<1];
ll edge[N<<1],ans;
void add(int x,int y,ll z){
    ver[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
    edge[tot]=z;
    ver[++tot]=x;
    Next[tot]=head[y];
    head[y]=tot;
    edge[tot]=0;
}
bool bfs(){
    for(int i=1;i<=t;i++)cur[i]=head[i],d[i]=0;
    d[s]=1;
    queue<int>q;
    q.push(s);
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(!d[y]&&edge[i]){
                d[y]=d[x]+1;
                q.push(y);
            }
        }
    }
    return (d[t]!=0);
}
ll dinic(int x,ll limit){
    if(x==t||!limit)return limit;
    ll flow=0,f;
    for(int &i=cur[x];i;i=Next[i]){
        int y=ver[i];
        if(d[y]==d[x]+1&&(f=dinic(y,min(limit,edge[i])))){
            flow+=f,limit-=f;
            edge[i]-=f,edge[i^1]+=f;
            if(!limit)break;
        }
    }
    return flow;
}
int main()
{
    scanf("%d%d",&m,&n);
    s=n+m+1,t=n+m+2;
    for(int i=1;i<=m;i++){
        scanf("%d",&c[i]);
        ans+=c[i];
        add(s,i,c[i]);
        char tools[10000];
        memset(tools,0,sizeof tools);
        cin.getline(tools,10000);
        int ulen=0,tool;
        while (sscanf(tools+ulen,"%d",&tool)==1)//之前已经用scanf读完了赞助商同意支付该实验的费用
        {//tool是该实验所需仪器的其中一个      
            //这一行，你可以将读进来的编号进行储存、处理，如连边。
            add(i,m+tool,inf);
            if (tool==0) 
                ulen++;
            else {
                while (tool) {
                    tool/=10;
                    ulen++;
                }
            }
            ulen++;
        }
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&p[i]);
        add(i+m,t,p[i]);
  //      printf("i:%d p:%d\n",i,p[i]);
    }
    ll flow=0;
    while(bfs()){
        flow+=dinic(s,inf);
    }
    for(int i=1;i<=m;i++)if(d[i])printf("%d ",i);
    printf("\n");
    for(int i=1;i<=n;i++)if(d[m+i])printf("%d ",i);
    printf("\n%lld\n",ans-flow);
    return 0;
}

$\ $

费用流

用SPFA代替bfs的部分，\(d[y]=d[x]+1\)改成\(d[y]=(d[x]+cost[i])_{min}\)
因为有负边权，所以在 \(dinic\) 里也要注意用 \(vis\) 来标记该点是否在栈中

$\ $

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10,M=5e4+10,inf=2147483647;
int n,m,s,t,ans,cur[N],d[N],vis[N];
int ver[M<<1],head[N],tot=1,Next[M<<1],edge[M<<1],cost[M<<1];
void add(int x,int y,int z,int c){
    ver[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
    edge[tot]=z;
    cost[tot]=c;
    ver[++tot]=x;
    Next[tot]=head[y];
    head[y]=tot;
    edge[tot]=0;
    cost[tot]=-c;
}
bool bfs(){
    for(int i=1;i<=n;i++)cur[i]=head[i],d[i]=inf,vis[i]=0;
    queue<int>q;
    d[s]=1;
    q.push(s);
    while(q.size()){
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(d[y]>d[x]+cost[i]&&edge[i]){
                d[y]=d[x]+cost[i];
                if(!vis[y]){
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
    return (d[t]!=inf);
}
int dinic(int x,int limit){
    if(x==t||!limit)return limit;
    int flow=0,f;
    vis[x]=1;
    for(int &i=cur[x];i;i=Next[i]){
        int y=ver[i];
        if(!vis[y]&&d[y]==d[x]+cost[i]&&(f=dinic(y,min(limit,edge[i])))){
            flow+=f,limit-=f;
            edge[i]-=f,edge[i^1]+=f;
            ans+=f*cost[i];
            if(!limit)break;
        }
    }
    vis[x]=0;
    return flow;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1,x,y,z,c;i<=m;i++){
        scanf("%d%d%d%d",&x,&y,&z,&c);
        add(x,y,z,c);
    }
    int flow=0;
    while(bfs()){
        flow+=dinic(s,inf);
    }
    printf("%d %d\n",flow,ans);
    return 0;
}

$\ $

继续学习ing……

标签：总结,阶段性,ver,int,flow,网络,edge,limit,return
From： https://www.cnblogs.com/chloris/p/17557681.html

相关文章

  • 暑假第一周总结
    周一：今天没有学习，在家玩了一天周二：今天看网课复习了一下python周三：今天进行python环境配置周四：今天玩了一天，没有学习。周五：今天进行数据库的连接。周六：今天继续连接数据库又看了一下爬虫的概念周日：今天玩了一天没有学习。......
  • 空间注意力机制 卷积神经网络
    空间注意力机制与卷积神经网络简介空间注意力机制是一种在卷积神经网络中引入的机制，用于加强模型对于特定区域的关注程度。传统的卷积神经网络对于每个位置的特征处理是相同的，而空间注意力机制则允许模型根据输入的不同位置自适应地调整特征的权重，从而更好地捕捉图像中的重要信息......
  • 性能分析工具总结
    CPU内存I/O参考资料Linux性能优化实战......
  • 暑假第一周总结
    第一周主要学习了python还有hadoop的前期内容，还有Linux的基本命令，shell的基本命令python里面学习了python的注释方法，python里面的基本的三个函数input（），print（），type（），python的格式化输出。Hadoop里面学习了Hadoop是什么，Hadoop的基本概念，Hadoop里面的三大分类HDFS，YARN，MapReduce。安装了......
  • CTO网络工程师：进制转换基础
    十进制：计数符号0到9  基数10计数规则逢十进一表示方法：101或（101）10 八进制计数符号0到7基数8计数规则逢八进一   二进制计数符号0到1基数2计数规则逢二进一  十六进制 基数16计数规则逢十六进一表示方法    ......
  • cto网络工程师：英语、数学
    英语：6%考试分值5分1、软考英语都考什么：直接从RFC文档内随便空出5个空要求大家完形填空先看后两个，然后一篇一篇去看三十篇文章可以百度翻译   数学：指数（有一半的概念都要用到指数的概念）、对数指数：    对数：   ......
  • 【网络】【TCP】TCP 协议有什么缺陷？
    1  前言这节我们来看个问题，就是 TCP协议有什么缺陷？TCP通过序列号、确认应答、超时重传、流量控制、拥塞控制等方式实现了可靠传输，看起来它很完美，事实真的是这样吗？TCP就没什么缺陷吗？所以，今天就跟大家聊聊，TCP协议有哪些缺陷？主要有四个方面：升级TCP的工作很困难；TCP建......
  • 【网络】【TCP】TCP Keepalive 和 HTTP Keep-Alive 是一个东西吗？
    1  前言这节我们来看个问题，就是 TCPKeepalive和HTTPKeep-Alive是一个东西吗？事实上，这两个完全是两样不同东西，实现的层面也不同：HTTP的Keep-Alive，是由应用层（用户态） 实现的，称为HTTP长连接；TCP的Keepalive，是由 TCP层（内核态） 实现的，称为TCP保活机制；接下来，分别......
  • 【网络】【TCP】如何基于 UDP 协议实现可靠传输？
    1  前言这节我们来看个问题，就是 TCP协议有什么缺陷？很多同学第一反应就会说把TCP可靠传输的特性（序列号、确认应答、超时重传、流量控制、拥塞控制）在应用层实现一遍。实现的思路确实这样没错，但是有没有想过，既然TCP天然支持可靠传输，为什么还需要基于UDP实现可靠传输呢？这......
  • 暑期 7.15 第一周博客总结
    在这一周中我学习了SSM的基本框架，学习了springboot与mybats等的基本知识，我也学习了b站上黑马程序员最新出的javaweb的视频教程，我又深入学习了一下javascri的语法。1.我学习了浏览器弹出框的警告：window.alert("")//浏览器弹出警示框document.alert("")//写入html在浏览器展示co......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99