为什么邻接表编号不能从0开始?

P3376 【模板】网络最大流

YellowBean_Elsa @ 2019-07-08 15:59:36

#include<bits/stdc++.h>
using namespace std;
const int inf=(1<<29);
int n,m,s,t;
int x,y,z,v[200010],w[200010],next[200010],first[20005],tot=1;//tot=-1就会错
int d[20005],maxflow;
queue<int> q;
inline int read(){
    int x=0;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+ch-48,ch=getchar();
    return x;
}
inline void add(int x,int y,int z){
    v[++tot]=y;w[tot]=z;
    next[tot]=first[x];
    first[x]=tot;
}
bool bfs(){
    memset(d,0,sizeof(d));
    while(q.size())q.pop();
    d[s]=1;q.push(s);
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=first[x];i;i=next[i]){
            int y=v[i];
            if(d[y] || !w[i])continue;
            d[y]=d[x]+1;
            q.push(y);
            if(y==t)return 1;
        }
    }
    return 0;
}
int dinic(int x,int flow){
    if(x==t)return flow;
    int rest=flow,k,y;
    for(int i=first[x];i&&rest;i=next[i]){
        if(!w[i] || d[y=v[i]]!=d[x]+1)continue;
        k=dinic(y,min(rest,w[i]));
        if(!k)d[y]=-1;
        w[i]-=k;w[i^1]+=k;
        rest-=k;
    }
    return flow-rest;
}
int main(){
    n=read();m=read();s=read();t=read();
    for(int i=1;i<=m;i++){
        x=read();y=read();z=read();
        add(x,y,z);add(y,x,0);
    }
    int f=0;
    while(bfs())
        while(f=dinic(s,inf))maxflow+=f;
    printf("%d\n",maxflow);
    return 0;
}

by yurzhang @ 2019-07-08 16:00:15

方便找反向边


by XeCtera @ 2019-07-08 16:02:10

@YellowBean

for(int i=first[x];i;i=next[i]){

查不到0的


by YellowBean_Elsa @ 2019-07-08 16:09:07

oh! Thanks!


by saipubw @ 2019-07-08 16:13:32

for(int i=first[x];i=-1;i=next[i])

然后你就可以从0开始了……

这点边界问题自己debug一下不久好了


by saipubw @ 2019-07-08 16:14:20

然后你还得把first初始化为-1


|