首页 > 代码库 > P3376 【模板】网络最大流
P3376 【模板】网络最大流
https://www.luogu.org/problem/show?pid=3376#sub
题目描述
如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。
输入输出格式
输入格式:
第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数ui、vi、wi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi)
输出格式:
一行,包含一个正整数,即为该网络的最大流。
输入输出样例
输入样例#1:
4 5 4 34 2 304 3 202 3 202 1 301 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。
1 #include <cstdio> 2 3 #define MIN(a,b) ( a<b ?a :b) 4 #define INF (1<<20) 5 6 using namespace std; 7 8 const int N(100000+15); 9 int n,m,s,t,u,v,w;10 int head[N<<1],sumedge;11 struct Edge12 {13 int to,next,val;14 Edge(int to=0,int next=0,int val=0):15 to(to),next(next),val(val){}16 }edge[N<<1];17 18 void ins(int from,int to,int val)19 {20 edge[++sumedge]=Edge(to,head[from],val);21 head[from]=sumedge;22 }23 24 int h,tail,que[N],deep[N];25 26 bool BFS(int t)27 {28 for(int i=1;i<=n;i++) deep[i]=-1;29 deep[s]=0; h=tail=0;que[tail++]=s;30 for(;h<tail;h++)31 {32 int front=que[h]; if(front==t) return true;33 for(int i=head[front];i;i=edge[i].next)34 {35 int go=edge[i].to;36 if(deep[go]<0&&edge[i].val)37 {38 deep[go]=deep[front]+1;39 que[tail++]=go;40 }41 }42 }43 return false;44 }45 46 int DFS(int now,int flow)47 {48 if(now==t||!flow) return flow;49 int flux=0;50 for(int i=head[now],go=edge[i].to;i;i=edge[i].next,go=edge[i].to)51 {52 if(deep[go]!=deep[now]+1||edge[i].val<=0) continue;53 int min=DFS( go, MIN(flow,edge[i].val) );54 flow-=min;55 flux+=min;56 edge[i].val-=min;57 edge[i^1].val+=min;58 if(!flow) return flux;59 }60 if(!flux) deep[now]=-1;61 return flux;62 }63 64 int Dinic(int s,int t)65 {66 int sum=0;67 for(;BFS(t);)68 sum+=DFS(s,INF);69 return sum;70 }71 72 int main()73 {74 scanf("%d%d%d%d",&n,&m,&s,&t);75 for(int i=1;i<=m;i++)76 {77 scanf("%d%d%d",&u,&v,&w);78 ins(u,v,w); ins(v,v,0);79 }80 int ans=Dinic(s,t);81 printf("%d\n",ans);82 return 0;83 }
P3376 【模板】网络最大流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。