这段代码为何会产生意料之外的结果,并在第 8~10 个测试点 RE?
查看原帖
这段代码为何会产生意料之外的结果,并在第 8~10 个测试点 RE?
786834
Herman526楼主2023/6/24 16:54

在解决网络流问题时,我使用了 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∼108\sim10 这 33 个连续的测试点竟然同时 RE 了!我下载了测试点 88,输入了数据,谁知,程序都没有运行完毕,也没有返回 00,便悄悄结束了。我想,这是不是因为 mm 值跳得不对呢?于是,我将加边的代码改成了这样:

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,12917527,30,1291752 前,mm 跳得都是正确的(在输入该边前,m=2054m=2054);而在输入以后,mm 却连续跳了 20252025 个数,一下变成了 2929。虽然变成 2929 以后的 mm 仍然每次只跳一个数,但也没有让程序逃过 RE 的命运。


看到这里,我更不明白了,为什么 mm 在输入这条特定的边前都“循规蹈矩”地每次只跳一个数,而后却一下打破了常规?这种“打破常规”与 RE 有实在的关系吗?

2023/6/24 16:54
加载中...