我有个猜想，你第一个代码break之后是不是就不会执行本次循环的```arc[u] = back[arc[u]]```了
by Edgebright @ 2023-09-22 17:18:03
这样的话下次搜进来，你的当前弧是满的
by Edgebright @ 2023-09-22 17:19:45
**这是我没看代码时写的**
你是不是一个开了o2优化，一个没开o2优化？因为o2优化会把for里的i++,j--变成++i,++j,时间大概快一倍（本人亲测过）
**这是我浅显看了代码后写的**
不仅有上面原因，把判断放外面会减小1点点计算量
by derekyang326 @ 2023-09-22 17:21:35
@[derekyang326](/user/1094313) 都说了不是常数问题了
by Bingxiu @ 2023-09-22 17:29:27
@[derekyang326](/user/1094313) 都说了不是常数问题 我不认为你有看懂费用流代码的能力
by hjqhs @ 2023-09-22 17:34:15
@[Edgebright](/user/762588) 经过测试，尽管这个确实有区别，但不是T的原因
by Edgebright @ 2023-09-22 18:25:43
```
bool broke = 0;
bool test(int sum, int maxi)
{
if(!broke) return sum<maxi;
else if(sum < maxi) return 1;
else assert(0);
}
int dfs(int u,int maxi) {
if (u == t) return maxi;
int sum=0,flow;in[u]=true;
for (; arc[u]&&test(sum, maxi); arc[u] = back[arc[u]]) {
v = to[arc[u]];
if (!in[v] && dist[v] == dist[u] + c[arc[u]]) {
flow= dfs(v,std::min(w[arc[u]], maxi - sum));
cg += flow* c[arc[u]], w[arc[u]] -= flow, w[arc[u] ^ 1] += flow, sum += flow;
if(sum >= maxi){
broke = 1; break;
}
}
}
in[u]=false;
return sum;
}
```
实测assert被触发了。这说明有些情况逃过了break但是被循环里的判断挡住了。
by Edgebright @ 2023-09-22 18:35:10
只有一种可以，就是maxi=0的情况。你的TLE代码会跑一遍循环然后break，AC代码会之间跳过。
特判maxi=0，实测AC.
by Edgebright @ 2023-09-22 18:49:57
@[Edgebright](/user/762588)
这个怎么解释
```cpp
//AC
#include<bits/stdc++.h>
#define ui unsigned int
#define au arc[u]
using namespace std;
const int nn=5002,mm=100005;
bool in[nn];
int n,m,s,t,u,v,fg,cg,tot=1;
int dist[nn],arc[nn],last[nn];
int to[mm],w[mm],c[mm],back[mm];
queue<int>q;
void link(int u,int v,int weight,int cost){
to[++tot]=v,w[tot]=weight,c[tot]=cost;
back[tot]=last[u],last[u]=tot;
}
bool spfa(){
memcpy(arc,last,sizeof last),
memset(dist,0x3f,sizeof dist);
for(q.push(s),in[s]=true,dist[s]=0;!q.empty();q.pop(),in[u]=false){
for(int i=last[u=q.front()];i;i=back[i]){
if(w[i]&&dist[v=to[i]]>dist[u]+c[i]){
dist[v]=dist[u]+c[i];
if(!in[v])q.push(v),in[v]=true;
}
}
}
return dist[t]!=1061109567;
}
int dinic(int u,int maxi){
if(u==t)return maxi;
int sum=0,f;in[u]=true;
for(;au;au=back[au]){
v=to[au];
if(!in[v]&&dist[v]==dist[u]+c[au]){
f=dinic(v,min(maxi-sum,w[au]));
sum+=f,cg+=f*c[au];
w[au]-=f,w[au^1]+=f;
}
if(sum==maxi)break;
}
in[u]=false;
return sum;
}
int main(){
int w,c;
for(scanf("%d%d%d%d",&n,&m,&s,&t);m--;)
scanf("%d%d%d%d",&u,&v,&w,&c),
link(u,v,w,c),link(v,u,0,-c);
while(spfa())
for(int flow;(flow=dinic(s,INT_MAX));)
fg+=flow;
printf("%d %d",fg,cg);
return 0;
}
```
```cpp
//TLE
#include<bits/stdc++.h>
#define ui unsigned int
#define au arc[u]
using namespace std;
const int nn=5002,mm=100005;
bool in[nn];
int n,m,s,t,u,v,fg,cg,tot=1;
int dist[nn],arc[nn],last[nn];
int to[mm],w[mm],c[mm],back[mm];
queue<int>q;
void link(int u,int v,int weight,int cost){
to[++tot]=v,w[tot]=weight,c[tot]=cost;
back[tot]=last[u],last[u]=tot;
}
bool spfa(){
memcpy(arc,last,sizeof last),
memset(dist,0x3f,sizeof dist);
for(q.push(s),in[s]=true,dist[s]=0;!q.empty();q.pop(),in[u]=false){
for(int i=last[u=q.front()];i;i=back[i]){
if(w[i]&&dist[v=to[i]]>dist[u]+c[i]){
dist[v]=dist[u]+c[i];
if(!in[v])q.push(v),in[v]=true;
}
}
}
return dist[t]!=1061109567;
}
int dinic(int u,int maxi){
if(u==t)return maxi;
int sum=0,f;in[u]=true;
for(;au;au=back[au]){
v=to[au];
if(!in[v]&&dist[v]==dist[u]+c[au]){
f=dinic(v,min(maxi-sum,w[au]));
sum+=f,cg+=f*c[au];
w[au]-=f,w[au^1]+=f;
if(sum==maxi)break;
}
}
in[u]=false;
return sum;
}
int main(){
int w,c;
for(scanf("%d%d%d%d",&n,&m,&s,&t);m--;)
scanf("%d%d%d%d",&u,&v,&w,&c),
link(u,v,w,c),link(v,u,0,-c);
while(spfa())
for(int flow;(flow=dinic(s,INT_MAX));)
fg+=flow;
printf("%d %d",fg,cg);
return 0;
}
```
纯粹只是把break调出来，而只有在大括号里面sum才会被修改，才有可能break啊，所以在不在里面是一样的。
by 千年知乎_天才 @ 2023-09-23 23:36:47
而且这不是巧合，另一道费用流的题，也是把break调出来就过了
https://www.luogu.com.cn/record/125835910
https://www.luogu.com.cn/record/125835940
by 千年知乎_天才 @ 2023-09-23 23:39:49