玄学,边从0开始编号,初始化为-1,能A,从2开始编号却只有70

P3376 【模板】网络最大流

LXH5514 @ 2021-05-25 14:14:17

第一种 : 边从0开始编号,邻接表first数组初始化为-1,能A, 提交记录

第二种 : 边从2开始编号,邻接表初始化为0,只有70分。 提交记录

第一种代码:

#include<iostream>
#include<stdio.h>
#include<queue>
#define int long long
using namespace std;
int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c-'0'),c=getchar();
    return x*f;
}
const int MAXN=5000*2,inf=0x7ffffff;
int n,m,s,t;
int u[MAXN],v[MAXN],first[MAXN],net[MAXN],val[MAXN],res[MAXN];
int cnt=0;
int first1[MAXN];
int level[MAXN];
void add(int x,int y,int z)
{

    u[cnt]=x;
    v[cnt]=y;
    val[cnt]=z;
    net[cnt]=first[x];
    first[x]=cnt;
    first1[x]=cnt;cnt++;
}
bool BFS()
{
    for(int i=1;i<=n;i++)
    first[i]=first1[i];
    for(int i=1;i<=n;i++)
    level[i]=0;
    level[s]=1;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=first[x];i!=-1;i=net[i])
        if(level[v[i]]==0&&val[i]!=0)level[v[i]]=level[x]+1,q.push(v[i]);
    }
    if(level[t]==0)return 0;
    return 1;
}
int dfs(int x,int y)
{
    if(x==t||y==0)return y;
    int sum=0;
    for(int i=first[x];i!=-1&&y-sum>0;i=net[i])
    {
        first[x]=i;
        if(level[v[i]]<=level[x]||val[i]==0)continue;
        if(sum==y)break;
        int z=dfs(v[i],min(val[i],y-sum));
        sum+=z;
        val[i]-=z;
        val[i^1]+=z;
    }
    return sum;
}
void liu()
{
    int ans=0;
    while(BFS())ans+=dfs(s,inf);
    printf("%lld\n",ans);
}
signed main()
{
    n=read();
    m=read();
    s=read();
    t=read();
    for(int i=1;i<=n;i++)
    first[i]=-1;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        x=read();
        y=read();
        z=read();
        add(x,y,z);
        add(y,x,0);
    }
    liu();
    return 0;
}

第二种:

#include<iostream>
#include<stdio.h>
#include<queue>
#define int long long
using namespace std;
int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c-'0'),c=getchar();
    return x*f;
}
const int MAXN=5000*2,inf=0x7ffffff;
int n,m,s,t;
int u[MAXN],v[MAXN],first[MAXN],net[MAXN],val[MAXN],res[MAXN];
int cnt=1;
int first1[MAXN];
int level[MAXN];
void add(int x,int y,int z)
{
    cnt++;
    u[cnt]=x;
    v[cnt]=y;
    val[cnt]=z;
    net[cnt]=first[x];
    first[x]=cnt;
    first1[x]=cnt;
}
bool BFS()
{
    for(int i=1;i<=n;i++)
    first[i]=first1[i];
    for(int i=1;i<=n;i++)
    level[i]=0;
    level[s]=1;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=first[x];i;i=net[i])
        if(level[v[i]]==0&&val[i]!=0)level[v[i]]=level[x]+1,q.push(v[i]);
    }
    if(level[t]==0)return 0;
    return 1;
}
int dfs(int x,int y)
{
    if(x==t||y==0)return y;
    int sum=0;
    for(int i=first[x];i&&y-sum>0;i=net[i])
    {
        first[x]=i;
        if(level[v[i]]<=level[x]||val[i]==0)continue;
        if(sum==y)break;
        int z=dfs(v[i],min(val[i],y-sum));
        sum+=z;
        val[i]-=z;
        val[i^1]+=z;
    }
    return sum;
}
void liu()
{
    int ans=0;
    while(BFS())ans+=dfs(s,inf);
    printf("%lld\n",ans);
}
signed main()
{
    n=read();
    m=read();
    s=read();
    t=read();
//  for(int i=1;i<=n;i++)
//  first[i]=-1;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        x=read();
        y=read();
        z=read();
        add(x,y,z);
        add(y,x,0);
    }
    liu();
    return 0;
}

核心代码基本没差,就是一些细节差别


by IntrepidStrayer @ 2021-05-25 14:28:31

你数组开小了


by LXH5514 @ 2021-05-25 14:31:10

%%%%% @star_duster


by Plozia @ 2021-05-25 14:31:16

maxn 随手加上 10 是个好习惯


by Plozia @ 2021-05-25 14:31:27

@LXH5514


by LXH5514 @ 2021-05-25 15:24:00

主要是我一开始只开了一倍的时候随手加了10,然后改成两倍就忘记加了


by 王瑞eggome @ 2021-05-25 18:22:18

%%%


|