萌新刚学OI,4AC6WA1TLE求调!

P3376 【模板】网络最大流

Eason2009 @ 2022-07-06 17:16:53

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,s,t,ans,head[205],now[205],to[10005],nex[10005],flow[10005],dis[205],tot;
void add(int u,int v,int w)
{
    tot++;
    to[tot]=v;
    flow[tot]=w;
    nex[tot]=head[u];
    head[u]=tot;
    return;
}
bool bfs()
{
    queue<int>q;
    memset(dis,0,sizeof(dis));
    dis[s]=1;
    q.push(s);
    now[s]=head[s];
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nex[i])
        {
            int v=to[i];
            if((!dis[v])&&flow[i])
            {
                now[v]=head[v];
                dis[v]=dis[u]+1;
                q.push(v);
                if(v==t)
                {
                    return 1;
                }
            }
        }
    }
    return 0;
}
int dfs(int u,int in)
{
    int sum=0;
    if(u==t) return in;
    for(int i=now[u];i;i=nex[i])
    {
        now[u]=i;
        int v=to[i];
        if(dis[v]==dis[u]+1&&flow[i])
        {
            int k=dfs(v,min(in,flow[i]));
            if(k==0) dis[v]=0;
            flow[i]-=k;
            flow[i^1]+=k;
            sum+=k;
            in-=k;
        }
    }
    return sum;
}
signed main()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,0);
    }
    while(bfs())
    {
        ans+=dfs(s,1e18);
    }
    cout<<ans;
    return 0;
}


by a1co0av5ce5az1cz0ap_ @ 2022-07-06 17:21:18

1TLE是什么鬼


by Eason2009 @ 2022-07-06 17:22:19

应该是没有用快读的原因,主要是WA的我很难受


by Maxwell_dcc @ 2022-07-06 17:32:36

@Eason2009 tot要初始化为1


by Eason2009 @ 2022-07-06 17:38:51

@Maxwell_dcc AC啦


|