73分求助

P3376 【模板】网络最大流

environmentalist @ 2021-11-05 19:23:29

样例八下载下来本地过了,在线IDE“输入长度不合法” ??

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
#define re register
#define in inline
using namespace std;
const ll inf=2147483647;
in ll read()
{
    ll x=0,k=1;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-') k=-1;
        c=getchar();
    }
    while(isdigit(c))
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*k;
}
ll z,ans;
int n,m,s,t;
int x,y;
struct eg{
    int v,nxt;
    ll w;
}edge[10001];
int head[5001],dis[5001],cnt=1,now[5001];
in void build(int u,int v,ll w)
{
    edge[++cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt;

    edge[++cnt].v=u;
    edge[cnt].w=0;
    edge[cnt].nxt=head[v];
    head[v]=cnt;
}   
in int bfs()
{
    for(re int i=1;i<=n;++i)
    {
        dis[i]=inf;
    }
    queue<int> q;
    q.push(s);
    dis[s]=0;
    now[s]=head[s];
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(re int i=head[u];i!=0;i=edge[i].nxt)
        {
            int v=edge[i].v;
            if(edge[i].w>0 and dis[v]==inf)
            {
                dis[v]=dis[u]+1;
                q.push(v);
                now[v]=head[v];
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
in ll dfs(int x,ll left)
{
    if(x==t) return left;
    ll k,out=0;
    for(re int i=now[x];i!=0 and left!=0;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(edge[i].w>0 and dis[v]==dis[x]+1)
        {
            k=dfs(v,min(left,edge[i].w));
            if(k==0) dis[v]=inf;
            left-=k,out+=k;
            edge[i].w-=k,edge[i^1].w+=k;
        }
    }
    return out;
}
in void dinic()
{
    while(bfs())
    {
        ans+=dfs(s,inf);
    }
}
int main()
{
    n=read(),m=read(),s=read(),t=read();
    for(re int i=1;i<=m;++i)
    {
        x=read(),y=read(),z=read();
        build(x,y,z);
    }
    dinic();
    printf("%lld",ans);
    return 0;
}

by JoaoFelix @ 2021-11-05 19:42:04

特尔施特根!


by environmentalist @ 2021-11-11 20:40:34

?确实(这不是重点)


|