上下界可行流
程序员文章站
2022-05-25 19:43:45
$RT$,无源汇上下界可行流就是一种没有源汇点的上下界可行流问题。# 题目
给出一个有向图。每条边有流量上界和下界,问是否存在一中流量分配方案,使得每个点流量守恒(即流入量=流出量)
思路
解决这种问题的主体思路就是在初始流的基础上不断添加流量,使得满足流 ......
无源汇上下界可行流
题目
给出一个有向图。每条边有流量上界和下界,问是否存在一中流量分配方案,使得每个点流量守恒(即流入量=流出量)
思路
解决这种问题的主体思路就是在初始流的基础上不断添加流量,使得满足流量守恒。
初始流很显然应该是每条边流量的下界。
但是这样并不满足流量守恒。然后考虑添加流量。
对于一个点,我们设初始流中他的流入量为\(rd\),流出量为\(cd\)。设\(d=rd-cd\)。
然后对\(d\)进行分类讨论。
如果\(d < 0\),则表示流入量要比流出量小,那么我们应该给多出来的流出量一个流出去的地方。所以就将点\(i\)向汇点t连一条容量为\(-d\)的边。
如果\(d > 0\),则表示流入量要比流出量大,那么我们应该给多出来的流入量一个来的地方。所以就从\(s\)向点\(i\)连一条容量为\(d\)的边。
如果\(d = 0\),那么流量已经守恒,就不用添加附加流了。
然后考虑怎么统计答案。
如果想要有可行流的话,那么\(s\)连出去的每条边必须满流,否则肯定没有可行流,这是一定的。
然后对于一条边他最终的流量应该是初始流+附加流。初始流就是流量下界。附加流就是反向边了。因为我们把减掉的流量都加到反向边上去了。
例题
代码
/* * @author: wxyww * @date: 2019-02-10 14:09:32 * @last modified time: 2019-02-10 14:26:40 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<queue> #include<cstring> #include<bitset> using namespace std; typedef long long ll; const int n = 200000,inf = 1e9; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int v,nxt,w; }e[n]; int head[n],ejs = 1; void add(int u,int v,int w) { e[++ejs].v = v;e[ejs].w = w;e[ejs].nxt = head[u];head[u] = ejs; e[++ejs].v = u;e[ejs].w = 0;e[ejs].nxt = head[v];head[v] = ejs; } queue<int>q; int dep[n],s,t; int rd[n],cur[n],cd[n]; int bfs() { memset(dep,0,sizeof(dep)); while(!q.empty()) q.pop(); dep[s] = 1;q.push(s); while(!q.empty()) { int u = q.front();q.pop(); for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(!dep[v] && e[i].w) { q.push(v); dep[v] = dep[u] + 1; if(v == t) return 1; } } } return 0; } int dfs(int u,int now) { if(u == t) return now; int ret = 0; for(int &i = cur[u];i;i = e[i].nxt) { int v = e[i].v; if(dep[v] == dep[u] + 1 && e[i].w) { int k = dfs(v,min(now - ret,e[i].w)); e[i].w -= k; e[i ^ 1].w += k; ret += k; if(now == ret) return ret; } } return ret; } int dinic() { int ans = 0; while(bfs()) { memcpy(cur,head,sizeof(cur)); ans += dfs(s,inf); } return ans; } int ans[n]; int low[n]; int main() { int n = read(),m = read(); s = n + 1,t = s + 1; for(int i = 1;i <= m;++i) { int u = read(),v = read();low[i] = read();int up = read(); add(u,v,up - low[i]); ans[i] = ejs; rd[v] += low[i];cd[u] += low[i]; } for(int i = 1;i <= n;++i) { int z = rd[i] - cd[i]; if(z > 0) add(s,i,z); if(z < 0) add(i,t,-z); } // puts("!!!"); dinic(); int bz = 0; for(int i = head[s];i;i = e[i].nxt) { if(e[i].w) { puts("no");return 0; } } puts("yes"); for(int i = 1;i <= m;++i) printf("%d\n",e[ans[i]].w + low[i]); return 0; }
有源汇上下界可行流
只要将\(t\)到\(s\)之间连一条容量为\(inf\)的边,就可以转化为无源汇上下界可行流了\(233\)。
推荐阅读
-
vue瀑布流组件实现上拉加载更多
-
高骈,写诗一流,打仗一流,却毁在了修仙上?
-
上下界可行流
-
飞鸽传书如何在win7/win8上通过媒体流共享图片和音乐视频的详细教程
-
【Python实现】运输问题的表上作业法:利用伏格尔 (Vogel) 法寻找初始基可行解
-
vue实现网络图片瀑布流 + 下拉刷新 + 上拉加载更多
-
Android Q无滚动长截图 谷歌:该功能在原生系统上不可行
-
Android Q无滚动长截图 谷歌:该功能在原生系统上不可行
-
最近想下m3u8格式视频流但是网址太卡好慢看不了所以搞了个python脚本下载 ,给有需要的也用用 ,可以有点小问题大家可以改改,搬或者移到其他视频流下载上,不要嫌弃
-
5.在第4题的基础上,重载流插入运算符