70分WA3点求好心dalao查错

P3376 【模板】网络最大流

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的反向边


|