首页 > 代码库 > P3376 【模板】网络最大流

P3376 【模板】网络最大流

2024-09-23 23:30:56   215人阅读

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 【模板】网络最大流


联系
我们