在解决网络流问题时,我使用了 ISAP。
#include<cstdio>
int h[201],e[5002],x[5002],r[201],d[201],q[201],g[201],n,m,s,t,u,v,z=1;
long long c[5002],w,l;
/*
h,x,c,e 分别为链式前向星的头指针、边的另一点、边权、后继;
r 是弧优化后的头指针,d 是点的深度,q 是队列,g[x] 是深度为 x 的点的个数
*/
bool y[201];
long long _(int a,long long b){
if(a==t)return l+=b,b;
long long f=0,o,p;
for(int i=r[a];i;i=e[i])if(c[i]&&d[x[r[a]=i]]+1==d[a]){
p=c[i];
if(p>b-f)p=b-f;
if(o=_(x[i],p)){
c[i]-=o,c[i^1]+=o;
if((f+=o)==b)return f;
}
}
if(!(--g[d[a]++]))d[s]=n;
g[d[a]]++;
return f;
}//dfs
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
while(m--){
scanf("%d%d%lld",&u,&v,&w);
if(u^v){
x[++z]=v,e[z]=h[u],c[h[u]=z]=w;
x[z|=1]=u,e[z]=h[v],h[v]=z;
}
}//添加双向边
y[q[0]=t]=1;
for(int i=0,j=1;i<j;i++)for(int k=h[q[i]];k;k=e[k])if(!y[x[k]])g[d[q[j++]=x[k]]=d[q[i]]+1]++,y[x[k]]=1;//bfs
while(d[s]<n){for(int i=1;i<=n;i++)r[i]=h[i];_(s,0x7fffffff);}
printf("%lld",l);
}
在提交代码时,我遇到了一个意想不到的情况——测试点中,8∼10 这 3 个连续的测试点竟然同时 RE 了!我下载了测试点 8,输入了数据,谁知,程序都没有运行完毕,也没有返回 0,便悄悄结束了。我想,这是不是因为 m 值跳得不对呢?于是,我将加边的代码改成了这样:
printf("%d.",m);
scanf("%d%d%lld",&u,&v,&w);
if(u^v){
x[++z]=v,e[z]=h[u],c[h[u]=z]=w;
x[z|=1]=u,e[z]=h[v],h[v]=z;
}
不出所料,在输入边 7,30,1291752 前,m 跳得都是正确的(在输入该边前,m=2054);而在输入以后,m 却连续跳了 2025 个数,一下变成了 29。虽然变成 29 以后的 m 仍然每次只跳一个数,但也没有让程序逃过 RE 的命运。
看到这里,我更不明白了,为什么 m 在输入这条特定的边前都“循规蹈矩”地每次只跳一个数,而后却一下打破了常规?这种“打破常规”与 RE 有实在的关系吗?