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 好的我知道了,谢谢奆佬