dChengx @ 2020-01-22 22:55:25
求助蒟蒻!!!
重打模板,TLE飞了
#include<bits/stdc++.h>
#define N 10005
#define M 200005
using namespace std;
const int inf=1e9;
int n,m,cnt=1,maxflow,d[N],S,T;
int ver[M],nx[M],v[M],fi[N];
queue<int> q;
void add(int x,int y,int z){
ver[++cnt]=y;nx[cnt]=fi[x];fi[x]=cnt;v[cnt]=z;
}
bool bfs(){
memset(d,0,sizeof(d));
q.push(S);
d[S]=1;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=fi[x];i;i=nx[i])
if(!d[ver[i]]&&v[i]){
int y=ver[i];
d[y]=d[x]+1;
q.push(y);
if(y==T)return 1;
}
}
return 0;
}
int dfs(int x,int flow){
if(x==T||!flow)return flow;
int ans,res=flow;
for(int i=fi[x],y=ver[i];i&&res;i=nx[i])
if(v[i]&&d[y]==d[x]+1){
ans=dfs(y,min(flow,v[i]));
if(!ans)d[y]=0;
v[i]-=ans;
v[i^1]+=ans;
res-=ans;
if(!res)return flow;
}
return flow-res;
}
void dinic(){
while(bfs())maxflow+=dfs(S,inf);
}
int main(){
scanf("%d%d%d%d",&n,&m,&S,&T);
for(int i=1;i<=m;i++){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
add(a,b,c);add(b,a,0);
}
dinic();
printf("%d",maxflow);
return 0;
}
by dChengx @ 2020-01-22 22:56:32
后来我又去蓝书上面找,这是我借鉴完蓝书之后的代码。。。
9TLE 1WA
by Wyxrg @ 2020-01-23 08:04:51
%%%
by Wyxrg @ 2020-01-23 08:48:30
看不出来诶
我好菜啊
by dChengx @ 2020-01-23 20:47:36
我更菜。。。
by dChengx @ 2020-01-23 21:19:29
我知道我哪错了
dinic函数里面与dfs里面有一个地方矛盾了:
if(!ans)d[y]=0;
原来这边是为了剪枝的
但是做完一遍dfs之后直接bfs了(在我的程序里)
所以剪枝无意义
所以从原来的dfs:
int dfs(int x,int flow){
if(x==T||!flow)return flow;
int ans,res=flow;
for(int i=fi[x],y=ver[i];i&&res;i=nx[i])
if(v[i]&&d[y]==d[x]+1){
ans=dfs(y,min(flow,v[i]));
if(!ans)d[y]=0;
v[i]-=ans;
v[i^1]+=ans;
res-=ans;
if(!res)return flow;
}
return flow-res;
}
变为
int dfs(int x,int flow){
if(x==t)return flow;
int now;
for(int i=fi[x];i;i=nx[i]){
int y=ver[i];
if(dep[y]!=dep[x]+1)continue;
now=dfs(y,min(flow,v[i]));
if(now){
v[i]-=now;
v[i^1]+=now;
return now;
}
}
return 0;
}
但本蒟蒻还有一个问题
就是这里
if(now){
v[i]-=now;
v[i^1]+=now;
return now;
}
这里直接返回答案确实没问题(有残余网络的话,bfs会判定的)
但为什么直接返回就不TLE了
求助dalao
by dChengx @ 2020-11-15 16:36:14
刚刚又学了一遍Dinic,貌似它一次dfs要增广多条路