henry_y @ 2018-03-13 22:58:13
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll int
#define M 100100
#define N 10010
#define inf 1<<30
#define mt(x,y) memset(x,y,sizeof(x))
#define max(x,y) x>y?x:y
#define min(x,y) x<y?x:y
#define abs(x) x>0?x:-x
#define mod 10000007
inline void read(ll &x){x=0;ll f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
using namespace std;
struct edge{ll to,next,v;}e[M<<1];
ll head[M],cnt=2;
ll q[N],h[N];//q为队列,h为分层
ll n,m,s,t;
inline void add(ll u,ll v,ll w){
e[++cnt].to=v;e[cnt].next=head[u];
e[cnt].v=w;head[u]=cnt;
}//邻接表
inline bool bfs(){//划分层次
ll l=0,r=1,now,i;
mt(h,-1);q[0]=s;h[s]=0;
while(l!=r){
now=q[l++];
for(i=head[now];i;i=e[i].next){
if(e[i].v&&h[e[i].to]==-1){
h[e[i].to]=h[now]+1;
q[r++]=e[i].to;
}
}
}
return h[t]!=-1;
}
inline ll dfs(ll x,ll f){//找增广路
if(x==t)return f;
ll w,i,used=0;
for(i=head[x];i;i=e[i].next){
if(h[e[i].to]==h[x]+1&&e[i].v){
w=dfs(e[i].to,min(f-used,e[i].v));
used+=w;e[i].v-=w;e[i^1].v+=w;
if(used==f)return f;
}
}
if(!used)h[x]=-1;
return used;
}
inline ll dinic(){
ll ans=0;
while(bfs())ans+=dfs(s,inf);
return ans;
}
int main(){
read(n);read(m);read(s);read(t);ll u,v,w;
for(ll i=1;i<=m;i++){
read(u);read(v);read(w);
add(u,v,w);add(v,u,0);
}
printf("%d",dinic());
return 0;
}
WA3个点,好心的dalao查查错?
by henry_y @ 2018-03-13 23:01:03
附: WA的点的测试数据: 数据输入:
10 25 2 10
3 4 4
4 3 45
3 5 80
1 6 94
3 7 63
9 8 92
1 9 75
6 3 12
7 9 63
6 1 39
6 1 97
9 7 33
7 4 55
8 9 36
5 2 61
9 8 97
2 4 36
1 2 2
10 2 14
5 9 82
5 1 32
6 2 94
9 2 10
6 10 50
7 6 53
数据输出:
36
我的输出:
178
by Night_Aurora @ 2018-03-14 07:49:03
cnt从1开始吧
by Night_Aurora @ 2018-03-14 07:49:17
@henry_y
by henry_y @ 2018-03-14 20:30:34
@Night_Aurora 谢谢dalaoqwq过了
by cn_lemon @ 2018-04-12 10:17:39
@henry_y 是的是的,我就是这么死的,蟹蟹你提这个问
by wangxuye @ 2018-05-15 20:53:41
@Night_Aurora 为什么cnt要从1开始
by laeva @ 2018-07-05 19:27:56
@wangxuye 1的反向边是0,而从1开始建边的话你默认2是1的反向边