为什么tot的值从1改成0就会炸

P3376 【模板】网络最大流

hwwqy @ 2023-10-16 11:46:04

#include<bits/stdc++.h>
#define int long long
#define inf 2147483647
using namespace std;
struct node{
    int nxt;
    int to;
    int val;
}e[10010];
int tot=0,now[210],head[210],dis[210];
int n,m,s,t;
void add(int u,int v,int val)
{
    e[++tot].to=v;
    e[tot].val=val;
    e[tot].nxt=head[u];
    head[u]=tot;

    e[++tot].to=u;
    e[tot].val=0;
    e[tot].nxt=head[v];
    head[v]=tot;
}
/*inline void add(int u,int v,long long w) {
    e[++tot].to=v;
    e[tot].val=w;
    e[tot].nxt=head[u];
    head[u]=tot;

    e[++tot].to=u;
    e[tot].val=0;
    e[tot].nxt=head[v];
    head[v]=tot;
}*/
int bfs()
{
    for(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 x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(e[i].val>0&&dis[v]==inf)
            {
                q.push(v);
                dis[v]=dis[x]+1;
                now[v]=head[v];
                if(v==t)return 1;
            }
        }
    }
    return 0;
}

int dfs(int x,int sum)
{
    if(x==t)return sum;
    int k,res=0;
    for(int i=now[x];i&&sum;i=e[i].nxt)
    {
        now[x]=i;
        int v=e[i].to;
        if(e[i].val>0&&(dis[v]==dis[x]+1)) {
            k=dfs(v,min(sum,e[i].val));
            if(k==0) dis[v]=inf;
            e[i].val-=k;
            e[i^1].val+=k;
            res+=k;
            sum-=k;
        }
    }
    return res;
}
int ans=0;
signed main()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        int u,v,e;
        cin>>u>>v>>e;
        add(u,v,e);
    }
    while(bfs())
    {
        ans+=dfs(s,inf);
    }
    cout<<ans;
    return 0;
}

++tot不应该是先加再计算吗,那e[1]不是会空出来吗


by lzyqwq @ 2023-10-16 11:47:48

是要把e[1]空出来啊,这样 ii^1 才是一对双向边


by hyj0824 @ 2023-10-16 12:02:49

因为你的链式前向星(链表)判断达到链表结尾时是 for(int i=head[x];i;i=e[i].nxt) ,是不能有编号为0的边的。除非你初始把head全赋值成 -1才行。


by Zikl @ 2023-10-16 22:16:30

e[i].val-=k;
e[i^1].val+=k;

因为上面这个东西,2^1=3,3^1=2。你的反向边就靠这个


by Kikcer @ 2023-11-28 20:31:59

感谢,找半天错看到你这个才知道错哪了


|