1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<queue> 6 using namespace std; 7 const int inf=1000000000,MAXN=100000+10,MAXM=1000000+10; 8 int to[MAXM],nex[MAXM],cap[MAXM],beg[MAXN],level[MAXN],n,m,s,t,e=1;//to，nex，cap与边有关，所以定MAXM，而beg，level与点有关，所以定MAXN，level用来分层，cap和flow两个数组缩减为一个cap，表示剩余的容量，节省空间 9 inline void read(int &x)10 {11     x=0;12     char c=getchar();13     while(c<‘0‘||c>‘9‘)c=getchar();14     while(c>=‘0‘&&c<=‘9‘)15     {16         x=(x<<3)+(x<<1)+(c^‘0‘);17         c=getchar();18     }19 }20 inline void insert(int x,int y,int z)//链式前向星加边21 {22     ++e;//e的初始值为1，因为后面将用到^（异或）23     to[e]=y;24     nex[e]=beg[x];25     beg[x]=e;26     cap[e]=z;27     ++e;28     to[e]=x;29     nex[e]=beg[y];30     beg[y]=e;31     cap[e]=0;32 }//网络流都是有向图，但要有反向弧，所以建两条，但反向的cap值初始化为0，因为正向没有流量时，反向是不能流的33 inline bool bfs()//BFS分层34 {35     memset(level,0,sizeof(level));//等级都初始化为036     level[s]=1;//起点等级为一，那么如果没有增广路到终点，返回时将会返回false37     queue<int> q;//定义BFS标准队列38     q.push(s);//起点入队39     while(!q.empty())//队列中还有未访问到的元素40     {41         int x=q.front();//去除队首元素42         q.pop();//删除队首元素43         for(register int i=beg[x];i;i=nex[i])//链式前向星标准循环44         {45             if(cap[i]&&!level[to[i]])//还有容量剩余并且该点未访问过46             {47                 level[to[i]]=level[x]+1;//赋等级48                 q.push(to[i]);//该点加入队列49             }50         }51     }52     return level[t];//如果还存在一条起点到终点的增广路，则返回true，否则返回false53 }54 inline int dfs(int x,int maxflow)//相当于EK的路径返回和加流量，DFS实现，x表示当前位置（点），maxflow表示之前的剩余容量的最大值55 {56     if(!maxflow||x==t)return maxflow;//如果没有剩余了或已经到终点了，直接返回57     int res=0;58     for(register int i=beg[x];i;i=nex[i])59     {60         if(cap[i]&&level[to[i]]==level[x]+1)//还有容量，并且该点到原位置的等级正好相差1，即连通并可行61         {62             int f=dfs(to[i],min(maxflow,cap[i]));//继续走下去，并将剩余容量与这条边的容量进行比较，更新剩余容量，即寻找瓶颈63             res+=f;//这条边上的最大流加上瓶颈64             maxflow-=f;//剩余容量最大值减去瓶颈65             cap[i]-=f;//该边剩余容量减去瓶颈66             cap[i^1]+=f;//该边反向边容量加上瓶颈67         }68     }69     return res;//返回70 }71 inline int Dinic()//Dinic求网络流最大流72 {73     int res=0;74     while(bfs())res+=dfs(s,inf);//res加上每一条从起点到终点的增广路上的最大流75     return res;76 }77 int main()78 {79     read(n);read(m);read(s);read(t);//s为起点，t为终点，n为点数，m为边数80     for(register int i=1;i<=m;++i)81     {82         int x,y,z;83         read(x);read(y);read(z);84         insert(x,y,z);85     }86     printf("%d",Dinic());87     return 0;88 }