有个小疑问

P3376 【模板】网络最大流

osfly @ 2022-06-28 22:04:23

在这份代码中

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m,s,t;
struct edge
{
    int v;
    int nxt;
    int w;
}e[5010<<1];
int head[1000],tot=1;
long long maxn=0;
void add(int u,int v,int w)
{
    e[++tot].v=v;
    e[tot].w=w;
    e[tot].nxt=head[u];
    head[u]=tot;
}
int d[1000];
int cur[1000];
bool bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            int w=e[i].w;
            if(!d[v]&&w)
            {
                d[v]=d[u]+1;
                q.push(v);
                if(v==t) return 1;  
            }
        }
    }
    return 0;
}
int dfs(int u,int flow)
{
    if(u==t) return flow;
    int rest=flow;
    for(int i=cur[u];i&&rest;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].v;
        int w=e[i].w;
        if(w&&d[v]==d[u]+1)
        {
            int k=dfs(v,min(rest,w));
            if(!k) d[v]=0;
            e[i].w-=k;
            e[i^1].w+=k;
            rest-=k;    
        }
     } 
    return flow-rest;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1,u,v,w;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,0);
    }
    int flow=0;
    while(bfs())
    {
        for(int i=1;i<=n;i++)
            cur[i]=head[i]; 
        while(flow=dfs(s,1<<29)) maxn+=flow;
    }
    printf("%lld",maxn);
    return 0;
}

如果将tot的初始值去掉(即去掉第15行中的=1)则会得到37分的好成绩

为什么?


by Smile_Cindy @ 2022-06-28 22:06:03

@osfly

如果tot不是从一开始的

那么i^1就不是i的反向边的编号


by 我是人999 @ 2022-06-28 22:21:10

楼上正解,补充几句:对于奇数 ii\oplus1=i-1,对于偶数有 i\oplus1=i+1,所以要保证第一条被加进去的边编号为偶数(可以认为 tot 初始值要置为 1)。


by Leonid @ 2022-07-09 08:15:55

@osfly 感谢。


by Anyakwi @ 2022-09-12 07:37:31

感谢


|