求助!!RE三个点

P3376 【模板】网络最大流

3493441984zz @ 2018-11-27 21:05:07


#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
struct Edge
{
    int to,nxt,dis;
}edge[100010];
int head[10010],cur[10010],deep[10010];
int n,m,s,t,ans,cnt=-1;
void add(int from,int to,int dis,int flag)
{
    edge[++cnt].to=to;
    edge[cnt].nxt=head[from];
    head[from]=cnt;
    if(flag)
        edge[cnt].dis=dis;
}
bool bfs()
{
    memset(deep,0x7f,sizeof(deep));
    for(int i=1;i<=n;++i)
        cur[i]=head[i];
    queue<int> dui;
    dui.push(s);
    deep[s]=0;
    while(!dui.empty())
    {
        int now=dui.front();
        dui.pop();
        for(int i=head[now];i!=-1;i=edge[i].nxt)
        {
            if(deep[edge[i].to]>inf&&edge[i].dis)
            {
                deep[edge[i].to]=deep[now]+1;
                dui.push(edge[i].to);
            }       
        }
    }
    if(deep[t]<inf)
        return 1;
    return 0;
}
int dfs(int now,int limit)
{
    if(!limit||now==t)
        return limit;
    int flow=0,f;
    for(int i=cur[now];i!=-1;i=edge[i].nxt)
    {
        cur[now]=i;
        if(deep[now]+1==deep[edge[i].to]&&(f=dfs(edge[i].to,min(limit,edge[i].dis))))
        {
            flow+=f;
            limit-=f;
            edge[i].dis-=f;
            edge[i^1].dis+=f;
            if(!limit)
                break;
        }
    }
    return flow;
}
void dinic()
{
    while(bfs())
        ans+=dfs(s,inf);
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;++i)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w,1);
        add(v,u,0,0);
    }
    dinic(); 
    printf("%d",ans);
    return 0;
} 

by y2823774827y @ 2018-11-27 21:20:46

@野心qwq %%%dalao


by y2823774827y @ 2018-11-27 21:21:08

@野心qwq M<=100000,数组开小了


by 3493441984zz @ 2018-11-28 19:59:10

@y2823774827y 哈哈哈,哪里比得上你,真的是


by 3493441984zz @ 2018-11-28 20:00:22

@y2823774827y 可是我还是RE了qwq


by 3493441984zz @ 2018-11-28 20:01:13

@y2823774827y 大佬帮忙找找错误呗


by 3493441984zz @ 2018-11-28 20:04:03

@y2823774827y AC了,开了1000000才AC是什么鬼。。。


by y2823774827y @ 2018-11-28 20:44:18

@野心qwq 双向边开200010过了


by 3493441984zz @ 2018-11-28 20:51:30

@y2823774827y 哦哦,不记得要双向边。。。


|