Echoternity @ 2022-07-07 21:11:36
WA了3个点,各位巨佬拜托了qwq
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=201;
const int MAXM=5001;
const int INF=0x7f7f7f7f;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
return x>y?x=y,1:0;
}
int N,M,S,T;
struct Graph
{
int next,to;
ll val;
Graph(int n=0,int t=0,ll v=0):next(n),to(t),val(v){}
}Edge[MAXM<<1];
int Head[MAXN],Cur[MAXN],Total=1;
inline void addEdge(int u,int v,ll w)
{
Edge[++Total]=Graph(Head[u],v,w);Head[u]=Total;
Edge[++Total]=Graph(Head[v],u,0);Head[v]=Total;
}
int Dep[MAXN],Num[MAXN];
inline void Bfs()
{
memset(Dep,-1,sizeof(Dep));
memset(Num,0,sizeof(Num));
Dep[T]=0,Num[0]=1;
queue<int>Q;
Q.push(T);
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int e=Head[u];e;e=Edge[e].next)
{
int v=Edge[e].to;
if(Dep[v]!=-1) continue;
Q.push(v);
Dep[v]=Dep[u]+1;
++Num[Dep[v]];
}
}
return ;
}
ll MaxFlow;
ll Dfs(int u,ll inf)
{
if(u==T)
{
MaxFlow+=inf;
return inf;
}
ll flow=0;
for(int e=Head[u];e;e=Edge[e].next)
{
Cur[u]=e;
int v=Edge[e].to;
if(Edge[e].val&&Dep[v]+1==Dep[u])
{
ll k=Dfs(v,min(Edge[e].val,inf-flow));
if(k)
{
Edge[e].val-=k;
Edge[e^1].val+=k;
flow+=k;
}
if(flow==inf) return flow;
}
}
--Num[Dep[u]];
if(Num[Dep[u]]==0) Dep[S]=N+1;
++Dep[u];
++Num[Dep[u]];
return flow;
}
inline int ISAP()
{
MaxFlow=0;
Bfs();
while(Dep[S]<N)
{
memcpy(Cur,Head,sizeof(Head));
Dfs(S,INF);
}
return MaxFlow;
}
int main()
{
// freopen("isap.in","r",stdin);
// freopen("isap.out","w",stdout);
read(N,M,S,T);
for(int i=1,u,v;i<=M;++i)
{
ll w;
read(u,v,w);
addEdge(u,v,w);
}
printf("%lld",ISAP());
return 0;
}
/*
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40
*/
by Echoternity @ 2022-07-07 21:47:38
又双叒叕把 long long
打成 int
了