bulijoijiodibuliduo @ 2021-06-01 21:34:22
基本抄刘汝佳蓝书上的代码，略有改动，结果WA了一个点。那个点的数据看起来很正常。应该没什么特殊情况。哪位奆老来帮帮忙！
#include<bits/stdc++.h>
#define int long long
const int N=5e4+10,M=2e5+10,inf=2e9;
using namespace std;
int now[N],head[N],to[M],nxt[M],cap[M],tot=1,d[N],pre[N],s,t,gap[N],n,e;
void addedge(int u,int v,int c){
tot++;
to[tot]=v;
cap[tot]=c;
nxt[tot]=head[u];
head[u]=tot;
}
void add(int u,int v,int c){
addedge(u,v,c);
addedge(v,u,0);
}
void bfs(){
queue<int>q;
q.push(t);
d[t]=1;
while(!q.empty()){
int x=q.front();
now[x]=head[x];
q.pop();
for(int i=head[x];i;i=nxt[i]){
int y=to[i],c=cap[i];
if(c==0&&!d[y]){
d[y]=d[x]+1;
q.push(y);
}
}
}
for(int i=1;i<=n;i++){
d[i]--;
}
}
int aug(){
int x=t;
int flow=inf;
while(x!=s){
flow=min(flow,cap[pre[x]]);
x=to[1^pre[x]];
}
x=t;
while(x!=s){
cap[pre[x]]-=flow;
cap[pre[x]^1]+=flow;
x=to[1^pre[x]];
}
return flow;
}
int maxflow(){
bfs();
int x=s,flow=0;
for(int i=1;i<=n;i++){
gap[d[i]]++;
}
while(d[s]<n){
if(x==t){
flow+=aug();
x=s;
}
bool ok=0;
for(int i=now[x];i;i=nxt[i]){
int c=cap[i],y=to[i];
if(c&&d[x]==d[y]+1){
ok=1;
pre[y]=i;
now[x]=i;
x=y;
break;
}
}
if(!ok){
int m=n-1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i],c=cap[i];
if(c)m=min(m,d[y]);
}
if(--gap[d[x]]==0)break;
gap[d[x]=m+1]++;
now[x]=head[x];
if(x!=s)x=to[pre[x]^1];
}
}
return flow;
}
signed main(){
cin>>n>>e>>s>>t;
for(int i=0;i<e;i++){
int u,v,c;
cin>>u>>v>>c;
add(u,v,c);
}
cout<<maxflow();
}
by bulijoijiodibuliduo @ 2021-06-01 21:41:16
已解决：
#include<bits/stdc++.h>
#define int long long
const int N=5e4+10,M=2e5+10,inf=2e9;
using namespace std;
int now[N],head[N],to[M],nxt[M],cap[M],tot=1,d[N],pre[N],s,t,gap[N],n,e;
void addedge(int u,int v,int c){
tot++;
to[tot]=v;
cap[tot]=c;
nxt[tot]=head[u];
head[u]=tot;
}
void add(int u,int v,int c){
addedge(u,v,c);
addedge(v,u,0);
}
void bfs(){
queue<int>q;
q.push(t);
for(int i=1;i<=n;i++){
d[i]=n;
}
d[t]=0;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=nxt[i]){
int y=to[i],c=cap[i];
if(c==0&&d[y]==n){
d[y]=d[x]+1;
q.push(y);
}
}
}
for(int i=1;i<=n;i++){
now[i]=head[i];
}
}
int aug(){
int x=t;
int flow=inf;
while(x!=s){
flow=min(flow,cap[pre[x]]);
x=to[1^pre[x]];
}
x=t;
while(x!=s){
cap[pre[x]]-=flow;
cap[pre[x]^1]+=flow;
x=to[1^pre[x]];
}
return flow;
}
int maxflow(){
bfs();
int x=s,flow=0;
for(int i=1;i<=n;i++){
gap[d[i]]++;
}
while(d[s]<n){
if(x==t){
flow+=aug();
x=s;
}
bool ok=0;
for(int i=now[x];i;i=nxt[i]){
int c=cap[i],y=to[i];
if(c&&d[x]==d[y]+1){
ok=1;
pre[y]=i;
now[x]=i;
x=y;
break;
}
}
if(!ok){
int m=n-1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i],c=cap[i];
if(c)m=min(m,d[y]);
}
if(--gap[d[x]]==0)break;
gap[d[x]=m+1]++;
now[x]=head[x];
if(x!=s)x=to[pre[x]^1];
}
}
return flow;
}
signed main(){
cin>>n>>e>>s>>t;
for(int i=0;i<e;i++){
int u,v,c;
cin>>u>>v>>c;
add(u,v,c);
}
cout<<maxflow();
}
by bulijoijoidibuliduo @ 2021-06-02 21:29:48
nb
by Moeebius @ 2021-10-21 20:23:07
qp(蓝书上代码貌似很多有问题，例如线段树，巨佬可以看看）@wdssean
by bulijoijiodibuliduo @ 2021-10-22 13:55:39
@xiaohuba 我发现是我bfs写的有问题，不是书的错，因为书上没写怎么bfs（而且我看的书好像是紫色的）