今天重写网络流时突然发现跑的特别慢( Link 1.02s)。

回去看了之前的代码(Link 67ms)。

发现写的完全一致，除了当前弧优化的实现方式：

慢的：

for(int &i=now[dq];i&∑i=Edge[i].nxt){
		int yy=Edge[i].y;
		if(Edge[i].v>0 && dis[yy]==dis[dq]+1){
			k=DFS(yy,min(sum,Edge[i].v));
			if(k==0) dis[yy]=INF;
			Edge[i].v-=k; sum-=k;
			Edge[i^1].v+=k; res+=k;
		}
	}return res;

快的：

for(int i=now[dq];i&∑i=Edge[i].nxt){
		int yy=Edge[i].y; now[dq]=i;
		if(Edge[i].v>0 && dis[yy]==dis[dq]+1){
			k=DFS(yy,min(sum,Edge[i].v));
			if(k==0) dis[yy]=INF;
			Edge[i].v-=k; sum-=k;
			Edge[i^1].v+=k; res+=k;
		}
	}return res;

不难发现，慢的使用了 & 符号直接更新了 $now$ 数组，而快的在进循环时显式更新，虽然看起来差不多，但在时间上相差了接近20倍。可是我已经用这种“慢”的方法闯过了好多网络流了，而且不少题解里的大佬也用的这种方法，怎么模板题里面相差这么多？？？(看起来就像没写一样…

不清楚为什么会有这种情况发生，取址的方法是错误的吗，求大佬解释……

完整代码在下面，已经控制变量法验证了二者只有上述地方不同，所以只放慢的：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 207;
const int M = 5007;
int ans;
int n,m;
int st,ed;
int now[N];
int dis[N];
int Link[N],l=1;
struct edge{int y,v,nxt;}Edge[M<<2];
inline void Insert(int x,int y,int v){
	l++;
	Edge[l].nxt=Link[x];
	Link[x]=l;
	Edge[l].y=y;
	Edge[l].v=v;
}
bool BFS(){
	for(int i=1;i<=n;i++) dis[i]=INF;
	queue <int> Q; Q.push(st);
	dis[st]=0; now[st]=Link[st];
	while(Q.empty()!=true){
		int dq=Q.front(); Q.pop();
		for(int i=Link[dq];i;i=Edge[i].nxt){
			int yy=Edge[i].y;
			if(Edge[i].v>0 && dis[yy]==INF){
				Q.push(yy);
				now[yy]=Link[yy];
				dis[yy]=dis[dq]+1;
				if(yy==ed) return true;
			}
		}
	}return false;
}
int DFS(int dq,int sum){
	if(dq==ed) return sum;
	int k,res=0;
	for(int &i=now[dq];i&&sum;i=Edge[i].nxt){
		int yy=Edge[i].y;
		if(Edge[i].v>0 && dis[yy]==dis[dq]+1){
			k=DFS(yy,min(sum,Edge[i].v));
			if(k==0) dis[yy]=INF;
			Edge[i].v-=k; sum-=k;
			Edge[i^1].v+=k; res+=k;
		}
	}return res;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>st>>ed;
	for(int i=1;i<=m;i++){
		int x,y,v;
		cin>>x>>y>>v;
		Insert(x,y,v);
		Insert(y,x,0);
	}while(BFS()) ans+=DFS(st,INF);
	cout<<ans;
	return 0;
}