wxk123 @ 2023-08-17 17:14:51
以我的代码为例子,请检查dfs函数中f=dfs处的参数是否打错了
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
int N,M,S,T;
#define int long long
const int MAXN=1000500;
struct B{
int u,v,w,next;
}p[5000005];
int head[1000500],cur[1000500],id=2;
int flag[205][205];
void build(int u,int v,int w){
p[id].u=u;
p[id].v=v;
p[id].w=w;
p[id].next=head[u];
head[u]=id;
id++;
}
int deep[MAXN];
bool bfs(int u,int t){queue<int>que;
memset(deep,-1,sizeof(deep));
for(int i=1;i<=N;i++)
cur[i]=head[i];
deep[u]=0;
que.push(u);
while(!que.empty()){
int uu=que.front();
que.pop();
for(int i=head[uu];i+1;i=p[i].next){
int v=p[i].v;
if(deep[v]==-1&&p[i].w>0){
deep[v]=deep[uu]+1;
que.push(v);
if(v==t)
return true;
}
}
}
if(deep[t]!=-1)
return true;
return false;
}
int dfs(int u,int minn){
int left=minn;
if(u==T||minn==0)
return minn;
int f=0;
for(int i=cur[u];i+1;i=p[i].next){
int v=p[i].v;
if(deep[u]+1==deep[v]&&p[i].w>0&&( f=dfs(v,min(left,p[i].w)))){ //我之前这里写的是dfs(v,min(minn,p[i].w)).....
left-=f;
p[i].w-=f;
p[i^1].w+=f;
}
if(!left)
break;
cur[u]=i;//注意当前弧优化的位置
}
return minn-left;
}
int dinic(int u,int v){
int ans=0;
while(bfs(u,v)){
ans+=dfs(u,0x3f3f3f3f3f3f3f3f);
}
return ans;
}
signed main(){
//freopen("1.in","r",stdin);
memset(head,-1,sizeof(head));
memset(cur,-1,sizeof(cur));
cin>>N>>M>>S>>T;
for(int i=1;i<=M;i++){
int u,v,w;
cin>>u>>v>>w;
// if(!flag[u][v]){
// flag[u][v]=id;flag[v][u]=id+1;
build(u,v,w);
build(v,u,0);
// }
// else{
// p[flag[u][v]].w+=w;
// }
}
cout<<dinic(S,T);
}
by Edgebright @ 2023-08-18 17:49:20
%%%谢谢大佬,刚好错了这个点
by renqitian @ 2023-12-07 01:48:38
太谢谢了,大佬orz