有源汇有上下界最小流(当前弧优化-->取地址就会超时，赋值秒过）

bdfs后无果

LOJ题面

两份代码不同，求助大佬:

ll dinic(ll u,ll tt,ll flow){
	if(u==tt)return flow;
	ll rst=flow,son;
	for(ll &i=strt[u];i;i=edge[i].nxt){
//	for(ll i=strt[u];i;i=edge[i].nxt){
//		strt[u]=i;
		if(rst==0)break;
		if(deep[edge[i].v]!=deep[u]+1||edge[i].c==0)continue;
		son=dinic(edge[i].v,tt,min(rst,edge[i].c));
		if(son==0)deep[edge[i].v]=0;
		edge[i].c-=son;edge[i^1].c+=son;rst-=son;
	}
	return flow-rst;
}

注释中的代码替换上面的循环后完全无压力通过，上述代码有一个1002ms

评测记录95pts

评测记录AC

全部代码：

#include<cstdio>
#include<cstring>
#define oo 2147483647ll
#define ll long long
using namespace std;
struct node{ll v,c,nxt;}edge[5000006];
ll head[1000006],cnt=1,strt[1000006];
void adge(ll u,ll v,ll c){
	edge[++cnt]=(node){v,c,head[u]};head[u]=cnt;
	edge[++cnt]=(node){u,0,head[v]};head[v]=cnt;
}
ll n,m;
ll S,T;
ll b[4000005],c[4000005];
ll ru[4000005],chu[4000005];
ll u[4000005],v[4000005];
ll Q[1000006],frt,rer;
ll deep[1000004];
bool vis[1000004];
ll min(ll a,ll b){return a<b?a:b;} 
bool bfs(ll ss,ll tt){
	ll u;
	frt=1,rer=0;
	for(ll i=0;i<=n+1;i++)deep[i]=0;
	Q[++rer]=ss;deep[ss]=1;
	while(rer-frt+1){
		u=Q[frt];frt++;
		for(ll i=head[u];i;i=edge[i].nxt){
			if(edge[i].c==0||deep[edge[i].v]!=0)continue;
			deep[edge[i].v]=deep[u]+1;
			Q[++rer]=edge[i].v;
			if(edge[i].v==tt)return true;			
		}
	}
	return false;
}
ll dinic(ll u,ll tt,ll flow){
	if(u==tt)return flow;
	ll rst=flow,son;
	for(ll &i=strt[u];i;i=edge[i].nxt){
//	for(ll i=strt[u];i;i=edge[i].nxt){
//		strt[u]=i;
		if(rst==0)break;
		if(deep[edge[i].v]!=deep[u]+1||edge[i].c==0)continue;
		son=dinic(edge[i].v,tt,min(rst,edge[i].c));
		if(son==0)deep[edge[i].v]=0;
		edge[i].c-=son;edge[i^1].c+=son;rst-=son;
	}
	return flow-rst;
}
int main(){//freopen("a.in","r",stdin);freopen("a.out","w",stdout);
	ll flow;
	ll ans=0;
	ll s,t;
	scanf("%lld%lld%lld%lld",&n,&m,&s,&t);S=0,T=n+1;
	adge(t,s,oo);
	for(ll i=1;i<=m;i++){
		scanf("%lld%lld%lld%lld",&u[i],&v[i],&b[i],&c[i]);
		adge(u[i],v[i],c[i]-b[i]);chu[u[i]]+=b[i];ru[v[i]]+=b[i];
	}
	for(ll i=1;i<=n;i++){
		if(ru[i]-chu[i]>=0)adge(S,i,ru[i]-chu[i]);
		else adge(i,T,chu[i]-ru[i]);
	}
	while(bfs(S,T)){
		for(int i=0;i<=n+1;i++)strt[i]=head[i];
		while(flow=dinic(S,T,oo));
	}
	ans+=edge[3].c;
	edge[2].c=edge[3].c=0;
	for(ll i=head[S];i;i=edge[i].nxt){
		if(edge[i].c!=0)return printf("please go home to sleep\n"),0;
		edge[i].c=edge[i^1].c=0;
	}
	for(ll i=head[T];i;i=edge[i].nxt){
		if(edge[i^1].c!=0)return printf("please go home to sleep\n"),0;
		edge[i].c=edge[i^1].c=0;
	}
	while(bfs(t,s)){
		for(int i=0;i<=n+1;i++)strt[i]=head[i];
		while(flow=dinic(t,s,oo))ans-=flow;
	}
	printf("%lld\n",ans);
	return 0;
}
 

洛谷上的费用流两份代码都是一样的速度，不太清楚为什么，求调谢谢