MnZn网络流37分求助+样例说明图疑似有误

P3376 【模板】网络最大流

_Ad_Astra_ @ 2022-07-24 14:02:56

RT.

样例图中1~3的flow应该为40,不是30

还有求助37分,TLE一个点WA6个点

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m,s,t,ans,lev[210],cnt,now[210],head[210];
struct node
{
    int to,nxt,flow;
    node(){}
    node(int _to,int _nxt,int _flow)
    {
        to=_to,nxt=_nxt,flow=_flow;
    } 
}g[10010];
void newedge(int u,int v,int flow)
{
    g[++cnt]=node(v,head[u],flow);
    head[u]=cnt;
    g[++cnt]=node(u,head[v],0);
    head[v]=cnt;
}
bool bfs(int s,int t)
{
    for(int i=1;i<=n;i++)lev[i]=inf;
    queue<int>q;
    q.push(s);
    lev[s]=0;
    now[s]=head[s];
    while(!q.empty())
    {
        int u=q.front();q.pop();
        int id=head[u];
        while(id)
        {
            int v=g[id].to;
            if(g[id].flow>0&&lev[v]==inf)
            {
                q.push(v);
                lev[v]=lev[u]+1;
                now[v]=head[v];
                if(v==t)return 1;
            }
            id=g[id].nxt;
        }
    }
    return 0;
}
int dinic(int u,int flow)
{
//  cout<<u<<' '<<flow<<endl;
    if(u==t)return flow;
    int ans=0,id=now[u];
    while(id&&flow)
    {
        now[u]=id;
        int v=g[id].to;
        if(g[id].flow>0&&lev[u]+1==lev[v])
        {
            int pflow=dinic(v,min(flow,g[id].flow));
            if(!pflow)lev[v]=inf;
            g[id].flow-=pflow;
            g[id^1].flow+=pflow;
            ans+=pflow;
            flow-=pflow;
        }
        id=g[id].nxt;
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        int u,v,flow;
        cin>>u>>v>>flow;
        newedge(u,v,flow);
    }
//  for(int i=1;i<=cnt;i++)cout<<g[i].to<<" "<<g[i].nxt<<" "<<g[i].flow<<endl;
    while(bfs(s,t))
    {
//      for(int i=1;i<=n;i++)cout<<lev[i]<<" ";
//      cout<<endl;
        ans+=dinic(s,inf);
//      for(int i=1;i<=n;i++)cout<<now[i]<<" ";
//      cout<<endl<<endl; 
    }
    cout<<ans;
    return 0;
}

by Resolute_Faith @ 2022-07-24 14:36:46

cnt一定要从1开始


by Resolute_Faith @ 2022-07-24 14:38:40

@Lehe


by _Ad_Astra_ @ 2022-07-24 14:39:43

@Resolute_Faith 刚刚过了,但还是谢谢QwQ


|