@[Alpha](/space/show?uid=87058) 啥，Dinic不对吗~~我才刚学~~
by _ztyqwq @ 2019-05-02 09:07:57
@[灯火丿葳蕤](/space/show?uid=73645)
我~~抄~~的Dinic
```cpp
#include <bits/stdc++.h>
#define int long long
#define MAXV 1000005
#define inf 2147483647
using std::queue;
using std::vector;
using std::min;
struct edge
{
int to,cap,rev;
};
vector<edge> G[MAXV];
int i,n,m,s,t,level[MAXV],iter[MAXV];
inline void read(int &x)
{
short negative=1;
x=0;
char c=getchar();
while(c<'0' || c>'9')
{
if(c=='-')
negative=-1;
c=getchar();
}
while(c>='0' && c<='9')
x=(x<<3)+(x<<1)+(c^48),c=getchar();
x*=negative;
}
inline void print(int x)
{
if (x<0)
putchar('-'),x=-x;
if(x>9)
print(x/10);
putchar(x%10+'0');
}
inline void add_edge(int from,int to,int cap)
{
G[from].push_back((edge){to,cap,G[to].size()});
G[to].push_back((edge){from,0,G[from].size()-1});
}
inline void bfs(int s)
{
memset(level,-1,sizeof(level));
queue<int> que;
level[s]=0;
que.push(s);
while(!que.empty())
{
int v=que.front();
que.pop();
for(int i=0;i<G[v].size();i++)
{
edge &e=G[v][i];
if (e.cap>0 && level[e.to]<0)
level[e.to]=level[v]+1,que.push(e.to);
}
}
}
inline int dfs(int v,int t,int f)
{
if (v==t)
return f;
for (int &i=iter[v];i<G[v].size();i++)
{
edge &e=G[v][i];
if (e.cap>0 && level[v]<level[e.to])
{
int d=dfs(e.to,t,min(f,e.cap));
if (d>0)
{
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
}
inline int max_flow(int s,int t)
{
int flow=0,f;
while (true)
{
bfs(s);
if (level[t]<0)
return flow;
memset(iter,0,sizeof(iter));
while((f=dfs(s,t,inf))>0)
flow+=f;
}
}
signed main(void)
{
read(n),read(m),read(s),read(t);
for (i=1;i<=m;i++)
{
int u,v,w;
read(u),read(v),read(w);
add_edge(u,v,w);
}
print(max_flow(s,t));
return 0;
}
```
by Smile_Cindy @ 2019-05-02 10:23:46