这是一个关于邻接表加上EK算法的问题

P3376 【模板】网络最大流

Fake_coder @ 2019-12-19 19:01:54

这是一个前向星存储的  但是发现改成^1的话3,4,5这三个测试点过不去  改成+1的话就过去了,哪个大佬可以给我解释一下?(是不是因为我太菜了??) 

/*************************************************************************
    > File Name: 网络流自己的版本.cpp
    > Author: Fake_coder
    > Mail: [email protected]
    > Created Time: Thu 19 Dec 2019 06:41:57 PM CST
 ************************************************************************/

#pragma o2
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<vector>
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,s,t;
#define MAXN 200001
struct node {
    int to,data,next;
};
int p=0;//记得一开始的值一定是0
int head[MAXN];//记录的是头
node e[MAXN];
void add(int front,int to,int data){
    e[++p].next=head[front];e[p].to=to;e[p].data=data;head[front]=p;
    e[++p].next=head[to];e[p].to=front;e[p].data=0;head[to]=p;//记得一开始的时候是0
}
int maxflow=0;//记录的就是答案
int front,to,data;
queue <int> q;//用来记录bfs函数的队列
int pre[MAXN];
int flow[MAXN];
void clear(){
    queue <int> empty;
    swap(empty,q);
}
int pr[MAXN];//用来记录所使用的边
int bfs(int s,int t){
    clear();
    for(int i=1;i<=n;i++){
        pre[i]=-1;
    }
    pre[s]=0;
    q.push(s);
    flow[s]=0x7ffffff;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        if(x==t){
            break;//因为找到一个就够了
        }
        for(int i=head[x];i;i=e[i].next){
            if(pre[e[i].to]==-1&&e[i].data>0){
                flow[e[i].to]=min(e[i].data,flow[x]);
                pre[e[i].to]=x;
                pr[e[i].to]=i;
                q.push(e[i].to);
            }
        }
    }
    if(pre[t]==-1){
        return -1;
    }
    else {
        return flow[t];
    }
}
void EK(int s,int t){
    int increase=0;
    while((increase=bfs(s,t))!=-1){
        int k=t;
        while(k!=s){
            e[pr[k]].data-=increase;
            e[pr[k]+1].data+=increase;//不知道为什么有一次改成^1过不去 改成+1就过去了
            k=pre[k];
        }
        maxflow+=increase;
    }

}
int main (){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&front,&to,&data);
        add(front,to,data);
    }
    EK(s,t);
    printf("%d",maxflow);
    return 0;
}

by Reaepita @ 2019-12-19 19:21:16

很显然的问题,你的边是从 1 开始编号的但是 1^1=0 ,并不是你所期望的方向边


by Fake_coder @ 2019-12-19 20:26:27

@WWWoWWW 好的我知道了,谢谢奆佬


|