正文
「模板」网络最大流 FF && EK && Dinic && SAP && ISAP
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
<题目链接>
话不多说上代码。
Ford-Fulkerson(FF)
#include <algorithm>
#include <climits>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=100010,MAXM=200010;
bool vis[MAXN];
int n,m,S,T,cnt,ans,head[MAXN];
struct edge
{
int nxt,to,w;
}e[MAXM];
void AddEdge(int x,int y,int w)
{
e[++cnt].nxt=head[x];
e[cnt].to=y;
e[cnt].w=w;
head[x]=cnt;
}
void AddEdges(int x,int y,int w)
{
AddEdge(x,y,w);
AddEdge(y,x,0);
}
int DFS(int x,int k)
{
if(x==T)
return k;
vis[x]=1;
for(int i=head[x],t,f;i;i=e[i].nxt)
if(!vis[t=e[i].to] && e[i].w && (f=DFS(t,min(k,e[i].w))))
{
e[i].w-=f;
e[((i-1)^1)+1].w+=f;
return f;
}
return 0;
}
void FF()
{
int f;
while(memset(vis,0,sizeof vis),f=DFS(S,INT_MAX))
ans+=f;
while(0,1)
printf("233");
while(1)
{
memset(vis,0,sizeof vis);
f=DFS(S,INT_MAX);
if(!f)
break;
ans+=f;
}
}
int main(int argc,char *argv[])
{
scanf("%d %d %d %d",&n,&m,&S,&T);
for(int i=1,x,y,w;i<=m;++i)
{
scanf("%d %d %d",&x,&y,&w);
AddEdges(x,y,w);
}
FF();
printf("%d\n",ans);
return 0;
}
Edmonds-Karp(EK)
#include <algorithm>
#include <climits>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN=10010,MAXM=200010;
int n,m,S,T,cnt,ans,head[MAXN],flow[MAXN],pre[MAXN],pre_e[MAXN];
struct edge
{
int nxt,to,w;
}e[MAXM];
void AddEdge(int x,int y,int w)
{
e[++cnt].nxt=head[x];
e[cnt].to=y;
e[cnt].w=w;
head[x]=cnt;
}
void AddEdges(int x,int y,int w)
{
AddEdge(x,y,w);
AddEdge(y,x,0);
}
bool BFS(int S)
{
queue<int> q;
memset(flow,0x7f,sizeof flow);
memset(pre,0,sizeof pre);
memset(pre_e,0,sizeof pre_e);
q.push(S);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x],t;i;i=e[i].nxt)
if(!pre[t=e[i].to] && e[i].w)
{
q.push(t);
pre[t]=x;
pre_e[t]=i;
flow[t]=min(flow[x],e[i].w);
}
if(pre[T])
return 1;
}
return 0;
}
void EK()
{
while(BFS(S))
{
for(int i=T,t;i!=S;i=pre[i])
{
e[t=pre_e[i]].w-=flow[T];
e[((t-1)^1)+1].w+=flow[T];
}
ans+=flow[T];
}
}
int main(int argc,char *argv[])
{
scanf("%d %d %d %d",&n,&m,&S,&T);
for(int i=1,x,y,w;i<=m;++i)
{
scanf("%d %d %d",&x,&y,&w);
AddEdges(x,y,w);
}
EK();
printf("%d",ans);
return 0;
}
Dinic
#include <algorithm>
#include <climits>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN=10010,MAXM=200010;
bool vis[MAXN];
int n,m,S,T,cnt,ans,head[MAXN],dis[MAXN],cur[MAXN];
struct edge
{
int nxt,to,w;
}e[MAXM];
void AddEdge(int x,int y,int w)
{
e[++cnt].nxt=head[x];
e[cnt].to=y;
e[cnt].w=w;
head[x]=cnt;
}
void AddEdges(int x,int y,int w)
{
AddEdge(x,y,w);
AddEdge(y,x,0);
}
bool BFS(int S)
{
queue<int> q;
memset(dis,0,sizeof dis);
vis[S]=1;
q.push(S);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x],t;i;i=e[i].nxt)
if(!vis[t=e[i].to] && e[i].w)
{
vis[t]=1;
q.push(t);
dis[t]=dis[x]+1;
}
if(dis[T])
return 1;
}
return 0;
}
int DFS(int x,int k)
{
if(x==T)
return k;
for(int i=cur[x],t,f;i;i=e[i].nxt)
if(dis[t=e[i].to]==dis[x]+1 && e[i].w && (f=DFS(t,min(k,e[i].w))))
{
e[i].w-=f;
e[((i-1)^1)+1].w+=f;
cur[x]=i;
return f;
}
return 0;
}
void Dinic()
{
int f;
while(memset(vis,0,sizeof vis),BFS(S))
while(memcpy(cur,head,sizeof head),f=DFS(S,INT_MAX))
ans+=f;
}
int main(int argc,char *argv[])
{
scanf("%d %d %d %d",&n,&m,&S,&T);
for(int i=1,x,y,w;i<=m;++i)
{
scanf("%d %d %d",&x,&y,&w);
AddEdges(x,y,w);
}
Dinic();
printf("%d",ans);
return 0;
}
Shortest Augmenting Path(SAP)
#include <algorithm>
#include <climits>
#include <cstdio>
#include <queue>
using namespace std;
const int MAXN=10010,MAXM=200010;
bool vis[MAXN];
int n,m,S,T,cnt,ans,head[MAXN],cur[MAXN],pre[MAXN],pre_e[MAXN],dis[MAXN],gap[MAXN];
struct edge
{
int nxt,to,w;
}e[MAXM];
void AddEdge(int x,int y,int w)
{
e[++cnt].nxt=head[x];
e[cnt].to=y;
e[cnt].w=w;
head[x]=cur[x]=cnt;
}
void AddEdges(int x,int y,int w)
{
AddEdge(x,y,w);
AddEdge(y,x,0);
}
void BFS(int T)
{
queue<int> q;
q.push(T);
vis[T]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x],t;i;i=e[i].nxt)
if(!dis[t=e[i].to] && !e[i].w)
{
vis[t]=1;
dis[t]=dis[x]+1;
q.push(t);
}
}
}
int Flow()
{
int f=INT_MAX;
for(int i=T;i!=S;i=pre[i])
f=min(f,e[pre_e[i]].w);
for(int i=T,t;i!=S;i=pre[i])
{
e[t=pre_e[i]].w-=f;
e[((t-1)^1)+1].w+=f;
}
return f;
}
void SAP()
{
BFS(T);
for(int i=1;i<=n;++i)
++gap[dis[i]];
int x=S;
while(dis[S]<n)
{
if(x==T)
{
ans+=Flow();
x=S;
}
bool flag=0;
for(int i=cur[x],t;i;i=e[i].nxt)
if(e[i].w && dis[x]==dis[t=e[i].to]+1)
{
flag=1;
pre[t]=x;
pre_e[t]=cur[x]=i;
x=t;
break;
}
if(!flag)
{
if(!--gap[dis[x]])
break;
int f=n-1;
for(int i=head[x];i;i=e[i].nxt)
if(e[i].w)
f=min(f,dis[e[i].to]);
++gap[dis[x]=f+1];
cur[x]=head[x];
if(x!=S)
x=pre[x];
}
}
}
int main(int argc,char *argv[])
{
scanf("%d %d %d %d",&n,&m,&S,&T);
for(int i=1,x,y,w;i<=m;++i)
{
scanf("%d %d %d",&x,&y,&w);
AddEdges(x,y,w);
}
SAP();
printf("%d",ans);
return 0;
}
Improved Shortest Augmenting Path(ISAP)
#include <algorithm>
#include <climits>
#include <cstdio>
using namespace std;
const int MAXN=10010,MAXM=200010;
int n,m,S,T,cnt,ans,head[MAXN],cur[MAXN],pre[MAXN],pre_e[MAXN],dis[MAXN],gap[MAXN];
struct edge
{
int nxt,to,w;
}e[MAXM];
void AddEdge(int x,int y,int w)
{
e[++cnt].nxt=head[x];
e[cnt].to=y;
e[cnt].w=w;
head[x]=cur[x]=cnt;
}
void AddEdges(int x,int y,int w)
{
AddEdge(x,y,w);
AddEdge(y,x,0);
}
int Flow()
{
int f=INT_MAX;
for(int i=T;i!=S;i=pre[i])
f=min(f,e[pre_e[i]].w);
for(int i=T,t;i!=S;i=pre[i])
{
e[t=pre_e[i]].w-=f;
e[((t-1)^1)+1].w+=f;
}
return f;
}
void ISAP()
{
for(int i=1;i<=n;++i)
++gap[dis[i]];
int x=S;
while(dis[S]<n)
{
if(x==T)
{
ans+=Flow();
x=S;
}
bool flag=0;
for(int i=cur[x],t;i;i=e[i].nxt)
if(e[i].w && dis[x]==dis[t=e[i].to]+1)
{
flag=1;
pre[t]=x;
pre_e[t]=cur[x]=i;
x=t;
break;
}
if(!flag)
{
if(!--gap[dis[x]])
break;
int f=n-1;
for(int i=head[x];i;i=e[i].nxt)
if(e[i].w)
f=min(f,dis[e[i].to]);
++gap[dis[x]=f+1];
cur[x]=head[x];
if(x!=S)
x=pre[x];
}
}
}
int main(int argc,char *argv[])
{
scanf("%d %d %d %d",&n,&m,&S,&T);
for(int i=1,x,y,w;i<=m;++i)
{
scanf("%d %d %d",&x,&y,&w);
AddEdges(x,y,w);
}
ISAP();
printf("%d",ans);
return 0;
}
「模板」网络最大流 FF && EK && Dinic && SAP && ISAP的更多相关文章- P3376 【模板】网络最大流( Edmonds-krap、Dinic、ISAP 算法)
P3376 [模板]网络最大流( Edmonds-krap.Dinic.ISAP 算法) 题目描述 如题,给出一个网络图,以及其源点和汇点,求出其网络最大流. 输入格式 第一行包含四个正整数N.M.S ...
- 图论算法-网络最大流【EK;Dinic】
图论算法-网络最大流模板[EK;Dinic] EK模板 每次找出增广后残量网络中的最小残量增加流量 const int inf=1e9; int n,m,s,t; struct node{int v, ...
- 【模板】网络最大流（EK、Dinic、ISAP）（网络流）/洛谷P3376
题目链接 https://www.luogu.com.cn/problem/P3376 题目大意 输入格式 第一行包含四个正整数 \(n,m,s,t\),分别表示点的个数.有向边的个数.源点序号.汇点 ...
- 「LuoguP3376」 【模板】网络最大流
题目描述 如题,给出一个网络图,以及其源点和汇点,求出其网络最大流. 输入输出格式 输入格式: 第一行包含四个正整数N.M.S.T,分别表示点的个数.有向边的个数.源点序号.汇点序号. 接下来M行每行 ...
- P3376 【模板】网络最大流(luogu)
P3376 [模板]网络最大流(luogu) 最大流的dinic算法模板(采取了多种优化) 优化 时间 inline+当前弧+炸点+多路增广 174ms no 当前弧 175ms no 炸点 249 ...
- P3376 【模板】网络最大流
P3376 [模板]网络最大流 题目描述 如题,给出一个网络图,以及其源点和汇点,求出其网络最大流. 输入输出格式 输入格式: 第一行包含四个正整数N.M.S.T,分别表示点的个数.有向边的个数.源点 ...
- 「HNOI2016」网络 解题报告
「HNOI2016」网络 我有一个绝妙的可持久化树套树思路,可惜的是,它的空间是\(n\log^2 n\)的... 注意到对一个询问,我们可以二分答案 然后统计经过这个点大于当前答案的路径条数,如果这 ...
- 「模板」 线段树——区间乘 && 区间加 && 区间求和
「模板」 线段树--区间乘 && 区间加 && 区间求和 原来的代码太恶心了,重贴一遍. #include <cstdio> int n,m; long l ...
- 「模板」 FHQ_Treap 区间翻转
「模板」 FHQ_Treap 区间翻转 没有旋转的 Treap 实现区间操作的功能,很好理解,也很好写,只是速度不算太快. 对于要翻转的区间,把整棵 Treap(存有区间 \([1,n]\) 的信息) ...
随机推荐- fragment的介绍与使用
稍稍摘录一段Fragment.java中的说明文档. /** * A Fragment is a piece of an application's user interface or behavio ...
- 左值&右值
一.引子 我们所谓的左值.右值,正确的说法应该是左值表达式.右值表达式. 因为C++的表达式不是左值就是右值. 在C中,左值指的是既能够出现在等号左边也能出现在等号右边的表达式,右值指的则是只能出现在 ...
- Java中I/O流之Print流
Java 中的 print 流: print 流用于做输出将会非常的方便,并且具有以下特点: 1. printWriter.printStream 都属于输出流,分别针对字符,字节. 2. print ...
- mysql的my.cnf配置文件
[client]port = 3306default-character-set=utf8mb4socket = /var/run/mysqld/mysql.sock# user=david# pas ...
- 硬盘引导扇区、多分区图、不通硬盘的LINUX逻辑分区数量
主要启动记录区(Master Boot Record,MBR):可以安装开机管理程序的地方,有446byte 分割表(Paritition table):记录整块硬盘分割的状态,有64bytes 下面 ...
- C# lamda表达式
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.T ...
- Qt信号与槽机制
一.信号和槽机制 信号和槽用于两个对象之间的通信,信号和槽机制是Qt的核心特征,也是Qt不同于其他开发框架的最突出的特征.在GUI编程中,当改变了一个部件时,总希望其他部件也能了解到该变化.更一般来说 ...
- shell脚本学习—条件测试和循环语句
条件测试 1. 条件测试:test [ 命令test或[可以测试一个条件是否成立,如果测试结果为真,则该命令的Exit Status为0,如果测试结果为假, 则命令的Exit Status为1(注意与 ...
- OI入门
学习顺序: 1.高精度计算: 高精度计算(一) 高精度计算练习1 高精度计算(二) 高精度计算练习2 2.递推 3.递归 递归算法 递归练习 4.搜索与回溯 搜索与回溯算法(一) 搜索与回溯练习(一) ...
- [BZOJ4036] [HAOI2015]按位或
传送门:https://lydsy.com/JudgeOnline/problem.php?id=4036 Description 刚开始你有一个数字0,每一秒钟你会随机选择一个[0,2^n-1]的数 ...
P3376 [模板]网络最大流( Edmonds-krap.Dinic.ISAP 算法) 题目描述 如题,给出一个网络图,以及其源点和汇点,求出其网络最大流. 输入格式 第一行包含四个正整数N.M.S ...
图论算法-网络最大流模板[EK;Dinic] EK模板 每次找出增广后残量网络中的最小残量增加流量 const int inf=1e9; int n,m,s,t; struct node{int v, ...
题目链接 https://www.luogu.com.cn/problem/P3376 题目大意 输入格式 第一行包含四个正整数 \(n,m,s,t\),分别表示点的个数.有向边的个数.源点序号.汇点 ...
题目描述 如题,给出一个网络图,以及其源点和汇点,求出其网络最大流. 输入输出格式 输入格式: 第一行包含四个正整数N.M.S.T,分别表示点的个数.有向边的个数.源点序号.汇点序号. 接下来M行每行 ...
P3376 [模板]网络最大流(luogu) 最大流的dinic算法模板(采取了多种优化) 优化 时间 inline+当前弧+炸点+多路增广 174ms no 当前弧 175ms no 炸点 249 ...
P3376 [模板]网络最大流 题目描述 如题,给出一个网络图,以及其源点和汇点,求出其网络最大流. 输入输出格式 输入格式: 第一行包含四个正整数N.M.S.T,分别表示点的个数.有向边的个数.源点 ...
「HNOI2016」网络 我有一个绝妙的可持久化树套树思路,可惜的是,它的空间是\(n\log^2 n\)的... 注意到对一个询问,我们可以二分答案 然后统计经过这个点大于当前答案的路径条数,如果这 ...
「模板」 线段树--区间乘 && 区间加 && 区间求和 原来的代码太恶心了,重贴一遍. #include <cstdio> int n,m; long l ...
「模板」 FHQ_Treap 区间翻转 没有旋转的 Treap 实现区间操作的功能,很好理解,也很好写,只是速度不算太快. 对于要翻转的区间,把整棵 Treap(存有区间 \([1,n]\) 的信息) ...
- fragment的介绍与使用
稍稍摘录一段Fragment.java中的说明文档. /** * A Fragment is a piece of an application's user interface or behavio ...
- 左值&右值
一.引子 我们所谓的左值.右值,正确的说法应该是左值表达式.右值表达式. 因为C++的表达式不是左值就是右值. 在C中,左值指的是既能够出现在等号左边也能出现在等号右边的表达式,右值指的则是只能出现在 ...
- Java中I/O流之Print流
Java 中的 print 流: print 流用于做输出将会非常的方便,并且具有以下特点: 1. printWriter.printStream 都属于输出流,分别针对字符,字节. 2. print ...
- mysql的my.cnf配置文件
[client]port = 3306default-character-set=utf8mb4socket = /var/run/mysqld/mysql.sock# user=david# pas ...
- 硬盘引导扇区、多分区图、不通硬盘的LINUX逻辑分区数量
主要启动记录区(Master Boot Record,MBR):可以安装开机管理程序的地方,有446byte 分割表(Paritition table):记录整块硬盘分割的状态,有64bytes 下面 ...
- C# lamda表达式
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.T ...
- Qt信号与槽机制
一.信号和槽机制 信号和槽用于两个对象之间的通信,信号和槽机制是Qt的核心特征,也是Qt不同于其他开发框架的最突出的特征.在GUI编程中,当改变了一个部件时,总希望其他部件也能了解到该变化.更一般来说 ...
- shell脚本学习—条件测试和循环语句
条件测试 1. 条件测试:test [ 命令test或[可以测试一个条件是否成立,如果测试结果为真,则该命令的Exit Status为0,如果测试结果为假, 则命令的Exit Status为1(注意与 ...
- OI入门
学习顺序: 1.高精度计算: 高精度计算(一) 高精度计算练习1 高精度计算(二) 高精度计算练习2 2.递推 3.递归 递归算法 递归练习 4.搜索与回溯 搜索与回溯算法(一) 搜索与回溯练习(一) ...
- [BZOJ4036] [HAOI2015]按位或
传送门:https://lydsy.com/JudgeOnline/problem.php?id=4036 Description 刚开始你有一个数字0,每一秒钟你会随机选择一个[0,2^n-1]的数 ...
