上下界网络流_weixin_30466421的博客-程序员秘密

本篇笔记写于远古时代,写时虽然参考了一些的资料(罗列在文末),但口胡仍然占多数,准确性堪忧,如有不准确的地方,欢迎指正。

无源汇有上下界可行流

首先要满足流量下界的需求,强行让每条边都流过low的流量,那么每条边只剩下的容量为upp-low,同时设流入点x的流量-流出点x的流量为d[x]。

考虑调整流网络使得流量平衡(让d[x]变为0)1)对于d[x]<0的点,我们希望向x流入-d[x]的流量 2)对于d[x]>0的点,我们希望从x流出d[x]的流量;

因此,考虑新建附源汇点S-T,S指向所有d[x]>0的x,所有d[x]>0的x指向T就能提供像这样调整的“势”。

对流网络跑最大流,如果存在边(S,?,k)或(?,T,k)满足k!=0,则可知无法调整到流量平衡,即不存在可行流。 因为sum a[x] (a[x]>0)=sum -a[x] (a[x]<0),具体操作时,只检差一边就行了。

显然,此时的一条边的可行流量为跑完最大流后所减少的流量(即反边流量)+原来的下界。

#include <bits/stdc++.h>
using namespace std;
const int N=207; 
const int L=30407;
const int inf=0x3f3f3f3f;

int S,T;
int head[N],to[L],cap[L],last[L],cnt=1;
int que[N],lev[N],hd,tl;

inline void add_edge(int x,int y,int c1,int c2=0) {
    to[++cnt]=y,cap[cnt]=c1,last[cnt]=head[x],head[x]=cnt;
    to[++cnt]=x,cap[cnt]=c2,last[cnt]=head[y],head[y]=cnt; 
}
inline bool bfs() {
    memset(lev,0,sizeof lev);
    lev[S]=1;
    que[hd=0,tl=1]=S;
    while(hd<tl) {
        int x=que[++hd];
        for(int i=head[x]; i; i=last[i]) if(cap[i]>0 && !lev[to[i]]) 
            lev[to[i]]=lev[x]+1, que[++tl]=to[i];
    }
    return lev[T]!=0;
}
int dfs(int x,int tf) {
    if(x==T) return tf;
    int tot=0,tmp;
    for(int i=head[x]; i; i=last[i]) if(cap[i]>0 && lev[x]+1==lev[to[i]]) {
        tmp=dfs(to[i],min(tf-tot,cap[i]));
        if(tmp) cap[i]-=tmp,cap[i^1]+=tmp,tot+=tmp;
        if(tot==tf) break;
    }
    if(!tot) lev[x]=-1;
    return tot;
}
int n,m,a[N],low[L]; 
bool check() {
    for(int i=head[S]; i; i=last[i]) 
        if(cap[i]) return false;
    for(int i=head[T]; i; i=last[i])
        if(cap[i^1]) return false;
    return true;
}
void solve() {
    cnt=1;
    memset(a,0,sizeof a);
    memset(head,0,sizeof head);
    for(int i=1,x,y,upp; i<=m; ++i) {
        scanf("%d%d%d%d",&x,&y,&low[i],&upp);
        a[x]-=low[i];
        a[y]+=low[i];
        add_edge(x,y,upp-low[i]);
    }
    int lst=cnt;
    S=n+1, T=n+2;
    for(int i=1; i<=n; ++i) {
        if(a[i]>0) add_edge(S,i,a[i]);
        if(a[i]<0) add_edge(i,T,-a[i]);
    }
    while(bfs()) dfs(S,inf);
    if(!check()) {
        puts("NO");
        return;
    }
    puts("YES"); 
    for(int i=2; i<=lst; i+=2) {
        printf("%d\n",cap[i^1]+low[i>>1]);
    }
}

int main() {
    while(~scanf("%d%d",&n,&m)) solve();
    return 0;
}

有源汇有上下界可行流

无源汇的流网络所有点都要满足d[x]=0,这说明它其实是一个“流循环图”。而对于有源汇的合法的流网络,除了d[s]<0,d[t]>0外,其余点满足d[x]=0,并且d[s]=-d[t],这启发我们加入t到s的一条下界为0,上界为inf的边,这样,图转化为一个“流循环图”,可以借助无源汇的算法调整。

来看下调整后流网络的边t-s,它的反边流量k=与s、t有关的基准流量,即这样的一组调整必然会给s-t的最大流带来k的贡献。答案即为k。

#include <bits/stdc++.h>
using namespace std;

const int N=207; 
const int L=30407;
const int inf=0x3f3f3f3f;

int S,T,s,t;
int head[N],to[L],cap[L],last[L],cnt=1;
int que[N],lev[N],hd,tl;

inline void add_edge(int x,int y,int c1,int c2=0) {
    to[++cnt]=y,cap[cnt]=c1,last[cnt]=head[x],head[x]=cnt;
    to[++cnt]=x,cap[cnt]=c2,last[cnt]=head[y],head[y]=cnt; 
}
inline bool bfs() {
    memset(lev,0,sizeof lev);
    lev[S]=1;
    que[hd=0,tl=1]=S;
    while(hd<tl) {
        int x=que[++hd];
        for(int i=head[x]; i; i=last[i]) if(cap[i]>0 && !lev[to[i]]) 
            lev[to[i]]=lev[x]+1, que[++tl]=to[i];
    }
    return lev[T]!=0;
}
int dfs(int x,int tf) {
    if(x==T) return tf;
    int tot=0,tmp;
    for(int i=head[x]; i; i=last[i]) if(cap[i]>0 && lev[x]+1==lev[to[i]]) {
        tmp=dfs(to[i],min(tf-tot,cap[i]));
        if(tmp) cap[i]-=tmp,cap[i^1]+=tmp,tot+=tmp;
        if(tot==tf) break;
    }
    if(!tot) lev[x]=-1;
    return tot;
}
int n,m,a[N],low[L]; 
bool check() {
    for(int i=head[S]; i; i=last[i]) 
        if(cap[i]) return false;
    for(int i=head[T]; i; i=last[i])
        if(cap[i^1]) return false;
    return true;
}
void solve() {
    cnt=1;
    memset(a,0,sizeof a);
    memset(head,0,sizeof head);
    for(int i=1,x,y,upp; i<=m; ++i) {
        scanf("%d%d%d%d",&x,&y,&low[i],&upp);
        a[x]-=low[i];
        a[y]+=low[i];
        add_edge(x,y,upp-low[i]);
    }
    add_edge(t,s,inf);
    S=n+1, T=n+2;
    for(int i=1; i<=n; ++i) {
        if(a[i]>0) add_edge(S,i,a[i]);
        if(a[i]<0) add_edge(i,T,-a[i]);
    }
    while(bfs()) dfs(S,inf);
    if(!check()) {
        puts("please go home to sleep");
        return;
    }
    printf("%d\n",upp[head[s]]);
}

int main() {
    while(~scanf("%d%d%d%d",&n,&m,&s,&t)) 
        solve();
    return 0;
}

有源汇有上下界最大流

接着第二来讲,因此,再将此边即所有与ST关联的边删除,剩下的便是张一般的流网络,k+此时s-t的最大流即为答案。

进一步的,我们可以不必删除t-s边和ST关联的边,直接采用当前流网络的s-t的最大流作为答案。因为1)t-s边的反边的基准流量必然会被增广;2)不可能存在经过S或T的增广路(S的出边、T的入边全部断开)。

#include <bits/stdc++.h>
using namespace std;

const int N=207; 
const int L=30407;
const int inf=0x3f3f3f3f;

int S,T,s,t;
int head[N],to[L],cap[L],last[L],cnt=1;
int que[N],lev[N],hd,tl;

inline void add_edge(int x,int y,int c1,int c2=0) {
    to[++cnt]=y,cap[cnt]=c1,last[cnt]=head[x],head[x]=cnt;
    to[++cnt]=x,cap[cnt]=c2,last[cnt]=head[y],head[y]=cnt; 
}
inline bool bfs() {
    memset(lev,0,sizeof lev);
    lev[S]=1;
    que[hd=0,tl=1]=S;
    while(hd<tl) {
        int x=que[++hd];
        for(int i=head[x]; i; i=last[i]) if(cap[i]>0 && !lev[to[i]]) 
            lev[to[i]]=lev[x]+1, que[++tl]=to[i];
    }
    return lev[T]!=0;
}
int dfs(int x,int tf) {
    if(x==T) return tf;
    int tot=0,tmp;
    for(int i=head[x]; i; i=last[i]) if(cap[i]>0 && lev[x]+1==lev[to[i]]) {
        tmp=dfs(to[i],min(tf-tot,cap[i]));
        if(tmp) cap[i]-=tmp,cap[i^1]+=tmp,tot+=tmp;
        if(tot==tf) break;
    }
    if(!tot) lev[x]=-1;
    return tot;
}
int n,m,a[N],low[L]; 
bool check() {
    for(int i=head[S]; i; i=last[i]) 
        if(cap[i]) return false;
    for(int i=head[T]; i; i=last[i])
        if(cap[i^1]) return false;
    return true;
}
void solve() {
    cnt=1;
    memset(a,0,sizeof a);
    memset(head,0,sizeof head);
    for(int i=1,x,y,upp; i<=m; ++i) {
        scanf("%d%d%d%d",&x,&y,&low[i],&upp);
        a[x]-=low[i];
        a[y]+=low[i];
        add_edge(x,y,upp-low[i]);
    }
    add_edge(t,s,inf);
    S=n+1, T=n+2;
    for(int i=1; i<=n; ++i) {
        if(a[i]>0) add_edge(S,i,a[i]);
        if(a[i]<0) add_edge(i,T,-a[i]);
    }
    while(bfs()) dfs(S,inf);
    if(!check()) {
        puts("please go home to sleep");
        return;
    }
    int ret=0;
    S=s, T=t;
    while(bfs()) ret+=dfs(S,inf);
    printf("%d\n",ret);
}

int main() {
    while(~scanf("%d%d%d%d",&n,&m,&s,&t)) 
        solve();
    return 0;
}

有源汇有上下界最小流

直接的做法是s-t的最小流=基准流量k - (t-s的最大流)。此时要注意删除t-s的边(若不删除,则会使得t-s的最大流接近无穷大,成功GG)。

#include <bits/stdc++.h>
#define LL long long 
using namespace std;

const int N=5e4+20;
const int L=2e6+20;
const LL inf=1e15;

int n,m,s,t,d[N];
int S=N-1,T=N-2;
int head[N],cur[N],to[L],last[L],cnt=1;
int que[N],lev[N],hd,tl;
LL upp[L];

inline void add_edge(int x,int y,LL u) {
    to[++cnt]=y,upp[cnt]=u,last[cnt]=head[x],head[x]=cnt;
    to[++cnt]=x,upp[cnt]=0,last[cnt]=head[y],head[y]=cnt; 
}
inline bool bfs() {
    memset(lev,0,(n+2)<<2);
    lev[S]=1;
    que[hd=0,tl=1]=S;
    while(hd<tl) {
        int x=que[++hd];
        for(int i=head[x]; i; i=last[i]) if(upp[i]>0 && !lev[to[i]]) 
            lev[to[i]]=lev[x]+1, que[++tl]=to[i];
    }
    return lev[T]!=0;
}
LL dfs(int x,LL tf) {
    if(x==T) return tf;
    LL tmp;
    for(int &i=cur[x]; i; i=last[i]) if(upp[i]>0 && lev[x]+1==lev[to[i]]) {
        tmp=dfs(to[i],min(tf,upp[i]));
        if(tmp) {
            upp[i]-=tmp;
            upp[i^1]+=tmp;
            return tmp;
        }
    }
    lev[x]=-1;
    return 0;
}
template<typename T> inline void read(T&d) {
    register char ch=getchar(); d=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) d=d*10+ch-'0',ch=getchar();
} 
LL dinic() {
    LL ret=0,tmp;
    while(bfs()) {
        for(int i=0; i<=n+1; ++i) cur[i]=head[i];
        while((tmp=dfs(S,inf))>0) ret+=tmp;
    }
    return ret;
}
int main() {
    read(n);read(m);read(s);read(t);
    for(int i=1,x,y,low,upp; i<=m; ++i) {
        read(x);read(y);read(low);read(upp);
        d[x]-=low;
        d[y]+=low;
        add_edge(x,y,upp-low); 
    }
    S=0, T=n+1;
    add_edge(t,s,inf);
    for(int i=1; i<=n; ++i) {
        if(d[i]>0) add_edge(S,i,d[i]);
        if(d[i]<0) add_edge(i,T,-d[i]);
    }
    dinic();
    for(int i=head[S]; i; i=last[i]) {
        if(upp[i]) {
            puts("please go home to sleep");
            return 0;
        }
    }
    long long st=upp[head[s]];
    upp[head[s]]=0;
    upp[head[t]]=0;
    S=t, T=s;
    printf("%lld\n",st-dinic());
    return 0;
}

无源汇有上下界最小费用可行流

干掉下界的时候,把费用先计算上。把超级源超级汇求最大流的一步,换成最小费用最大流即可。即满足合法的前提下,最小化费用。费用就是之前的费用加上这次的费用。

有源汇有上下界最小费用可行流

参考第一到第二的转化,添加边t-s,下界为0,上界为inf,费用为0。然后按照第五进行调整至所有点流量平衡即可。

有源汇有上下界最小费用最大流

似乎直接按照第三改一波。。mf改为mcmf。

有源汇有上下界最小费用最小流

似乎直接按照第四改一波。。我也不清楚,因为要减去最多的花费 最大费用流???

参考资料:

学习笔记 上下界网络流 作者*Miracle*。

网络流常见建模总结 作者panda_2134。

转载于:https://www.cnblogs.com/nosta/p/10938396.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30466421/article/details/95982662

智能推荐

logrotate的使用以及注意事项_夏目-的博客-程序员秘密_logrotate 重启

第4条是自己补充的,其他内容转发自:https://blog.csdn.net/u010039418/article/details/81045632注:本文基于CentOS 7.2编写,logrotate版本为logrotate-3.8.6-6.el7.x86_64logrotate用于日志转储,可以根据用户配置的规则,将日志转储,或者删除,防止陈年旧账占满磁盘空间。下面介绍一些注意事项,防止有人掉坑里。1、logrotate依赖cron任务执行我们先看下logrotate这个组件有哪些文.

java前台接口调用,Java 接口调用_亿升笑的博客-程序员秘密

/*** 向指定 URL 发送POST方法的请求* @param url 发送请求的 URL* @param params 请求的参数集合* @return 远程资源的响应结果*/private String sendPost(String url, Map params) {OutputStreamWriter out = null;BufferedReader in = null;String...

pytorch_a69432的博客-程序员秘密

一、Torch与NumpyTorch可以把tensor放到GPU加速上训练,就像Numpy把array放到CPU上训练一样。torch tensor和numpy array的相互转换tensor=torch.from_numpy(array)array=tensor.numpy() 1 import torch 2 import numpy as np 3...

android APK打包过程学习_艾伦蓝的博客-程序员秘密

[size=medium][b]流程概述:[/b][/size]1、打包资源文件,生成R.java文件2、处理aidl文件,生成相应java 文件[color=red]3、编译工程源代码,生成相应class 文件[/color]4、转换所有class文件,生成classes.dex文件5、打包生成apk6、对apk文件进行签名[b]7、对签名后的apk文件进行对齐处理[...

usb hub和usb device注册过程_xiaofengcanyue2013的博客-程序员秘密

A10的cpu有一个hub,也就是root hub,下边带有三个controller。其中第0个控制器具有otg功能,它的端点0支持最大64字节的控制传送,另外具有5个端点;控制器1、2只能作为host用,其下面最多能外接一个hub。如果控制器0作为device用,简称udc;如果作为host用,就和其他两个控制器一样简称hcd。     他们作为平台设备注册进内核,平台资源在drivers/

Hive学习(一)Hive的三种搭建方式_Hen_YA的博客-程序员秘密

Hive三种搭建方式一、Local本地(derby)元数据库derby与工具都是在本地只需将压缩包解压,在hive-site.xml做以下配置(将原信息删除)注:需要将hive-site.xml.template更名为hive-site.xmlmv hive-default.xml.template hive-site.xml&amp;amp;amp;amp;lt;?xml version=&amp;amp;amp;quot;1.0&amp;amp;amp;quot;?&amp;amp;amp;

随便推点

JS+CSS实现的非常漂亮的橘黄色滑动门_weixin_34067102的博客-程序员秘密

代码简介:JS+CSS实现的非常漂亮的橘黄色滑动门,记得有个CSS文件,很棒的。代码内容:&lt;!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"&gt;&lt;html xmlns="ht...

推荐一个Arduino学习模拟器: 123D Circuites_iracer的博客-程序员秘密_arduino模拟器

123D Circuites是AutoDesk发布的一个专业电子模拟器网站,网址为:https://123d.circuits.io/ 你可以通过虚拟Arduino 板和实验电路板来研究电子问题,可以使用内置的代码编辑器进行Arduino 编程和仿真,方便用户进行原理性验证和实验。

kubernetes入门_Kubernetes入门:一个kubectl速查表_cukw6666的博客-程序员秘密

kubernetes 入门 介绍 (Introduction)Kubectl is a command-line tool designed to manage Kubernetes objects and clusters. It provides a command-line interface for performing common operations like creating a...

字节跳动2022校招内推_高聪江的博客-程序员秘密

字节跳动2022校招研发提前批内部推荐全面启动!冲啊!!!【超快流程】所有岗位无笔试!直接面试更畅快【超稳通关】多一次投递机会,提前批投递结果不影响秋招字节跳动校招内推码: Q26GEKV投递链接: https://jobs.toutiao.com/s/egGJqLH通过此链接投递全程跟进投递状态!...

java实验4 发牌程序_是zg啊!的博客-程序员秘密_发牌程序java

题目类别: 实验关键字: 掌握Java数组、方法的基本定义内容要求:编写程序,项目名和类名均为PokerGame。实现功能:(1) 共有m幅扑克牌,每幅扑克牌不包括大王和小王共52张牌。(2) 可能有n个人参与扑克游戏,2&lt;=n&lt;=52。(3) 程序运行时输入扑克牌幅数m和人数n,然后所有牌分别依次分发给n个人。不能整除时,每个人的牌数可以不同,如3个人1幅牌,则第1个人18张,第2个和第3个人17张牌。(4) 发牌完成后按花色(顺序为黑桃、红心、草花、方块)和牌面大小输出每个

自适应滤波:维纳滤波器——LCMV及MVDR实现_weixin_33734785的博客-程序员秘密

作者:桂。时间:2017-03-24  06:52:36链接:http://www.cnblogs.com/xingshansi/p/6609317.html 声明:欢迎被转载,不过记得注明出处哦~ 【读书笔记03】前言西蒙.赫金的《自适应滤波器原理》第四版,上一篇看到维纳滤波基本形式:最优化问题,且无任何条件约束。这次看到有约束的部分,简单整理一下思路: ...

推荐文章

热门文章

相关标签