QTcyy @ 2020-09-12 14:25:29
人都傻了啊放在其他题里都能A的在这里不行了qwq
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1000005;
const LL INF = 0x3f3f3f3f3f3f3f3f;
struct node{
LL s;
int to,next;
};
node que[N];
int head[N],dis[N];
bool vis[N];
int cnt=1,n,m,s,t;
inline void add(int u,int v,LL w){
que[cnt].s=w;
que[cnt].to=v;
que[cnt].next=head[u];
head[u]=cnt++;
return;
}
inline bool bfs(){
memset(dis,-1,sizeof(dis));
queue<int>q;
dis[s]=1;
q.push(s);
while (!q.empty()){
int u=q.front();
q.pop();
for (int i=head[u];i!=-1;i=que[i].next){
int k=que[i].to;
if (dis[k]==-1 && que[i].s){
dis[k]=dis[u]+1;
q.push(k);
if (k==t)
return true;
}
}
}
return false;
}
LL dfs(int x,LL now){
if (x==t)
return now;
LL delta=now,tmp=0;
for (int i=head[x];i!=-1;i=que[i].next){
int k=que[i].to;
if (dis[k]==dis[x]+1 && que[i].s){
tmp=dfs(k,min(delta,que[i].s));
if (!tmp){
dis[k]=0;
continue;
}
delta-=tmp;
que[i].s-=tmp;
que[i^1].s+=tmp;
if (!delta)
break;
}
}
return now-delta;
}
inline LL dinic(){
LL ans=0,now=0;
while (bfs())
while (now=dfs(s,INF))
ans+=now;
return ans;
}
signed main(void){
memset(head,-1,sizeof(head));
scanf("%d%d%d%d",&n,&m,&s,&t);
for (int i=1;i<=m;i++){
int a,b;LL c;
scanf("%d%d%lld",&a,&b,&c);
add(a,b,c);
add(b,a,0);
}
printf("%lld\n",dinic());
return 0;
}
by 幻影星坚强 @ 2020-09-12 14:29:39
要加当前弧优化才不能T,WA就不知道了()