zyywzw @ 2019-08-03 17:58:43
RT
#include<bits/stdc++.h>
#define REP(i,a,b) for(register int i(a);i<=b;i++)
using namespace std;
const int N=1e4+100;
const int M=1e5+100;
const int INF=2e8+10;
int n,m,s,t,x,y,z,maxflow;
int head[N],cur[N],tot=-1;
struct edge{int to,nxt,cap;}G[M<<1];
int dep[N],use[N];
template<class T>inline void read(T&x){
T r=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){r=r*10+ch-'0';ch=getchar();}
x=r*f;
}
inline void add(int x,int y,int z){G[++tot]=(edge){y,head[x],z};head[x]=tot;}
inline int BFS(){
queue<int>q;
memset(dep,-1,sizeof(dep));
q.push(s);dep[s]=0;
while(q.size()){
int u=q.front();q.pop();
for(register int i=head[u];i;i=G[i].nxt){
int v=G[i].to;
if(dep[v]==-1&&G[i].cap)
{dep[v]=dep[u]+1;q.push(v);}
}
}
return dep[t]!=-1;
}
inline int dfs(int u,int f){
if(u==t)return f;
int lft,used=0;
for(register int i=cur[u];i;i=G[i].nxt){
if(dep[G[i].to]==dep[u]+1&&G[i].cap){
lft=f-used;lft=dfs(G[i].to,min(G[i].cap,lft));
G[i].cap-=lft;if(G[i].cap)cur[u]=i;
G[i^1].cap+=lft;used+=lft;
}
}
if(!used)dep[u]=-1;
return used;
}
inline void Dinic(){
while(BFS()){
REP(i,1,n)cur[i]=head[i];
maxflow+=dfs(s,INF);
}
cout<<maxflow;
}
int main(){
read(n);read(m);read(s);read(t);
REP(i,1,m){read(x);read(y);read(z);
add(x,y,z);add(y,x,0);}
Dinic();
}
by Vn_nV @ 2019-08-03 17:59:37
洛谷数据水
by 塔罗兰 @ 2019-08-03 18:20:56
我更好奇你样例都没过是怎么有勇气交上去的