P3376 【模板】网络最大流

题目描述

如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。

输入输出格式

输入格式:

第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含三个正整数ui、vi、wi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi)

输出格式:

一行,包含一个正整数,即为该网络的最大流。

输入输出样例

输入样例#1:

4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40

输出样例#1:

50

说明

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=10,M<=25

对于70%的数据:N<=200,M<=1000

对于100%的数据:N<=10000,M<=100000

样例说明:

题目中存在3条路径:

4-->2-->3,该路线可通过20的流量

4-->3,可通过20的流量

4-->2-->1-->3,可通过10的流量(边4-->2之前已经耗费了20的流量)

故流量总计20+20+10=50。输出50。

看了几本教材发现都没有用边表去写网络流的,于是自己琢磨了很长时间,

用的是Dinic算法

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 #include<algorithm>
  7 #define lli long long int 
  8 using namespace std;
  9 const int MAXN=300001;
 10 const int maxn=0x7fffff;
 11 void read(int &n)
 12 {
 13     char c='+';int x=0;bool flag=0;
 14     while(c<'0'||c>'9')
 15     {c=getchar();if(c=='-')flag=1;}
 16     while(c>='0'&&c<='9')
 17     {x=x*10+c-48;c=getchar();}
 18     flag==1?n=-x:n=x;
 19 }
 20 struct node
 21 {
 22     int u,v,flow,cap,nxt;
 23 }edge[MAXN];
 24 int head[MAXN];
 25 int num=0;
 26 int n,m,S,T;
 27 int dis[MAXN];
 28 int vis[MAXN];
 29 int cur[MAXN];
 30 void add_edge(int x,int y,int z)
 31 {
 32     edge[num].u=x;
 33     edge[num].v=y;
 34     edge[num].cap=z;
 35     edge[num].flow=0;
 36     edge[num].nxt=head[x];
 37     head[x]=num++;
 38 }
 39 bool bfs(int bg,int ed)
 40 {
 41     memset(dis,-1,sizeof(dis));
 42     queue<int>q;
 43     q.push(bg);
 44     dis[bg]=0;
 45     while(!q.empty())
 46     {
 47         int p=q.front();
 48         q.pop();
 49         for(int i=head[p];i!=-1;i=edge[i].nxt)
 50         {
 51             if(dis[edge[i].v]==-1&&edge[i].cap>edge[i].flow)
 52             {
 53                 vis[edge[i].v]=1;
 54                 dis[edge[i].v]=dis[edge[i].u]+1;
 55                   q.push(edge[i].v);            
 56             }
 57         }
 58     }
 59     if(dis[ed]==-1)
 60         return 0;
 61     else return 1;
 62 }
 63 int dfs(int now,int a)// a:所有弧的最小残量 
 64 {
 65     if(now==T||a<=0)
 66         return a;
 67         
 68     int flow=0,f;
 69     for(int i=head[now];i!=-1;i=edge[i].nxt)
 70     {
 71         if(dis[now]+1==dis[edge[i].v]&&edge[i].cap-edge[i].flow>0)
 72         {
 73             f=dfs(edge[i].v,min(a,edge[i].cap-edge[i].flow));
 74             edge[i].flow+=f;
 75             edge[i^1].flow-=f;
 76             flow+=f;
 77             a-=f;
 78             if(a<=0)break;
 79         }
 80     }
 81     return flow;
 82 }
 83 void Dinic(int S,int T)
 84 {
 85     int ansflow=0;
 86     for(int i=1;i<=n;i++)
 87             cur[i]=head[i];
 88     while(bfs(S,T))// 求出层级
 89         ansflow+=dfs(S,maxn); 
 90     printf("%d",ansflow);
 91     
 92 }
 93 int main()
 94 {
 95     read(n);read(m);
 96 //    swap(n,m);
 97 //    S=1;T=m;
 98     read(S);read(T);
 99     for(int i=1;i<=n;i++)
100         head[i]=-1;
101     for(int i=1;i<=m;i++)
102     {
103         int x,y,z;
104         read(x);read(y);read(z);
105         add_edge(x,y,z);
106         add_edge(y,x,0);
107     }
108     Dinic(S,T);
109     return 0;
110 }

update in 2017.7.29

补充一份加了当前弧优化&&把cap和flow两个变量合成一个的代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<algorithm>
 7 using namespace std;
 8 const int MAXN=10000001;
 9 const int MAXM=30000001;
10 const int maxn=0x7fffff;
11 inline void read(int &n)
12 {
13     char c='+';int x=0;bool flag=0;
14     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
15     while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
16     flag==1?n=-x:n=x;
17 }
18 struct node
19 {
20     int u,v,f,nxt;
21 }edge[MAXM];
22 int head[MAXN];
23 int num=0;
24 int n,m,s,t;
25 inline void add_edge(int x,int y,int z)
26 {
27     edge[num].u=x;
28     edge[num].v=y;
29     edge[num].f=z;
30     edge[num].nxt=head[x];
31     head[x]=num++;
32 }
33 int ans=0;
34 int deep[MAXN];
35 int cur[MAXN];
36 inline bool bfs()
37 {
38     memset(deep,0,sizeof(deep));
39     deep[s]=1;
40     queue<int>q;
41     q.push(s);
42     while(q.size()!=0)
43     {
44         int p=q.front();
45         q.pop();
46         for(int i=head[p];i!=-1;i=edge[i].nxt)
47             if(!deep[edge[i].v]&&edge[i].f)
48             {
49                 deep[edge[i].v]=deep[edge[i].u]+1;
50                 q.push(edge[i].v);
51             }
52                 
53     }
54     return deep[t];
55 }
56 int dfs(int now,int a)
57 {
58     if(now==t||a<=0)
59         return a;
60     int totflow=0,curflow;
61     for(int &i=cur[now];i!=-1;i=edge[i].nxt)
62     {
63         if(edge[i].f&&deep[edge[i].v]==deep[edge[i].u]+1)
64         {
65             curflow=dfs(edge[i].v,min(a,edge[i].f));
66             edge[i].f-=curflow;
67             edge[i^1].f+=curflow;
68             totflow+=curflow;
69             a-=curflow;
70             if(a<=0) break;
71         }
72     }
73     return totflow;
74 }
75 inline void Dinic()
76 {
77     while(bfs())
78     {
79         for(int i=0;i<=n;i++)
80             cur[i]=head[i];
81         ans+=dfs(s,maxn);
82     }
83         
84     printf("%d",ans);
85 }
86 int main()
87 {
88     read(n);read(m);read(s);read(t);
89     memset(head,-1,sizeof(head));
90     for(int i=1;i<=m;i++)
91     {
92         int x,y,z;
93         read(x);read(y);read(z);
94         add_edge(x,y,z);
95         add_edge(y,x,0);
96     }
97     Dinic();
98     return 0;
99 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技大本营的专栏

你一定能看懂的算法基础书(代码示例基于Python)

本文引自图灵教育《算法图解》 你一定能看懂的算法基础书;代码示例基于Python;400多个示意图,生动介绍算法执行过程;展示不同算法在性能方面的优缺点;教会...

58270
来自专栏窗户

平方根的C语言实现(一) —— 浮点数的存储

  曾经做一个硬件成本极度控制的项目,因为硬件成本极低,并且还需要实现较高的精度测量,过程中也自己用C语言实现了正弦、余弦、反正切、平方根等函数。   以下,无...

450100
来自专栏前端吧啦吧啦

数据结构(一)之基础知识

11840
来自专栏Brian

R语言性能Tips和GC

最近团队在使用R语言作为算法的实践语言,通过人工策略和xgboost算法进行一些价格算法的控制和输出,发现一些代码中对于内存、CPU、程序设计思想以及现代统计算...

14900
来自专栏前端吧啦吧啦

数据结构(一)之基础知识

376100
来自专栏Eugene's Blog

一文总结学习 Python的14 张思维导图分类目录文章标签友情链接联系我们

13740
来自专栏ACM算法日常

ACM之坑&amp;套路

写在前边:这些梗都是敝人自己做题和比赛时曾经坑过自己的地方,特别在这里记录一下,所有的链接都是本博客中的题解链接(有大致题意说明和代码),原题请到OJ上自行寻找...

9820
来自专栏机器学习AI算法工程

【手把手教你做项目】自然语言处理:单词抽取/统计

作者 白宁超 成都信息工程大学硕士。 近期关注数据分析统计学、机器学习。 原文:http://www.cnblogs.com/baiboy/p/zryy1.h...

373130
来自专栏Crossin的编程教室

【每周一坑】乒乓数

刚从假期回来,又要迎接周末,各位看官想必都很辛苦,所以本周每周一坑为大家准备一道简单的甜点题目,本题取材于伯克利大学 CS61 课程 homework02。 求...

33060
来自专栏数据结构与算法

2152 滑雪

2152 滑雪  时间限制: 1 s  空间限制: 32000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 题目描述 Description t...

28480

扫码关注云+社区

领取腾讯云代金券