事实上不建反向边都能过
by Flaranis @ 2018-05-17 21:40:46
```cpp
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define REG register
const int maxn=2e6+5;
const int inf=0x3f3f3fll;
#define min(a,b) a<b?a:b
typedef long long ll;
struct Input{
#define SIZE 20000
char BUF[SIZE],*S,*T;
Input():S(BUF),T(BUF){}
inline char Getchar(){return((S==T)&&(T=(S=BUF)+fread(BUF,1,SIZE,stdin),S==T)?EOF:*S++);}
inline Input&operator>>(char&c){return(c=Getchar(),*this);}
inline Input&operator>>(int&s){
s=0;REG char c;
while(c=Getchar(),c<48||c>57);
while(s=s*10+c-48,c=Getchar(),c>47&&c<58);
return*this;
}inline Input&operator>>(ll&s){
s=0;REG char c;
while(c=Getchar(),c<48||c>57);
while(s=(ll)s*10+c-48,c=Getchar(),c>47&&c<58);
return*this;
}
#undef SIZE
}input;
struct Output{
#define SIZE 20000
char BUF[SIZE],*S,*Limit;
Output():S(BUF),Limit(BUF+SIZE){}
~Output(){fwrite(BUF,1,S-BUF,stdout);}
inline void Flush(){fwrite(BUF,1,S-BUF,stdout);S=BUF;}
inline void Putchar(const char&c){if(S==Limit)Flush();*S++=c;}
inline Output&operator<<(const char&c){return(Putchar(c),*this);}
template<class T>inline Output&operator<<(T s){
static char Stack[20];static int Top;
Top=0;do Stack[++Top]=s%10+48;while(s/=10);
while(Top)Putchar(Stack[Top--]);
return*this;
}
}output;
int head[maxn],p=-1;
int cur[maxn],G[maxn],depth[maxn];
int S,T,n,m,u,v,w;
struct Edge{
int v,nxt,w;
}s[maxn<<2];
inline void add(REG int u,REG int v,REG int w)
{
s[++p]=(Edge){v,head[u],w};
head[u]=p;
return;
}
inline void Add_Edge(REG int u,REG int v,REG int w)
{
add(u,v,w);
add(v,u,0);
return;
}
inline void bfs()
{
queue<int> Q;
while(!Q.empty()) Q.pop();
memset(G,0,sizeof(G));
memset(depth,0,sizeof(depth));
depth[S]=1;
Q.push(S);
do
{
int x=Q.front();
Q.pop();
for(REG int i=head[x];i;i=s[i].nxt)
{
int to=s[i].v;
if(s[i].w>0&&!depth[to])
{
depth[to]=depth[x]+1;
Q.push(to);
}
}
}while(!Q.empty());
return;
}
inline int dfs(REG int u,REG int val)
{
if(u==T) return val;
int ans=0;
for(REG int&i=cur[u];i;i=s[i].nxt)
{
int to=s[i].v;
if(depth[to]==depth[u]+1&&s[i].w>0)
{
int ok=dfs(to,min(val,s[i].w));
ans+=ok;
val-=ok;
s[i^1].w+=ok;
}//
if(!val) return ans;
}
if(!(--G[depth[u]])) depth[S]=n+1;//
++G[++depth[u]];//
cur[u]=head[u];//
return ans;
}
inline int ISAP()
{
bfs();
int flow=dfs(S,inf);
while(depth[S]<=n) flow+=dfs(S,inf);
return flow;
}
int main()
{
input>>n>>m>>S>>T;
for(REG int i=1;i<=m;i++)
{
input>>u>>v>>w;
Add_Edge(u,v,w);
}
output<<ISAP();
return 0;
}
```
by Explorer_CYC @ 2018-05-20 16:11:29