警示后人 WA#1/2/3/6/12

我的实现模式是封装化最大次大值答案，使用四元素排序直接计算。

洛谷不支持数据下载，后来在校内 OJ 上面获取到了数据并且发现错误。

同时 WA #3/#6/#12 很有可能是代码逻辑问题，这个问题可能很严重，但是数据太水没验证出来。比如我倍增跳 LCA 的过程之中把大于号写成了小于号。提供两组 hack 数据，一组小数据和一组大数据，
同时 WA #10/#12 大概率是基本错误，比如 long long 上限较低、没有用 LL 统计答案。
WA #1/2 是没有判断自环，这点需要注意程序的鲁棒性。

另外，建议本题开放数据下载，毕竟此题未开放数据下载的条件下要想独立做出来还是比较困难的。

另外，重边等边权的情况下应该判断无解。不过本题一定有解。

另外，贴一份我封装化最大次大值求解此题的代码，毕竟封装化求解最大次大比较简洁，但是没什么人写：：

CPP

#include<bits/stdc++.h>
#define fo(i,a,b) for(I i=(a);i<=(b);++i)
#define fd(i,a,b) for(I i=(a);i>=(b);--i)
#define gch(w) for(;w(CH);CH=getchar())
const int inf=0x3f3f3f3f;
using namespace std;using I=int;using LL=long long;using V=void;I CH,FL;template<typename T>V in(T&a){a=0;FL=1;gch(!isdigit)FL=(CH=='-')?-1:1;gch(isdigit)a=a*10+CH-'0';a*=FL;}template<typename T,typename...Args>V in(T&a,Args&...args){in(a);in(args...);}
const I N=1e5+10,M=3e5+10;
I ey[N<<1],hd[N],nx[N<<1],ec,ez[N<<1];
V conn(I x,I y,I z){ey[++ec]=y;nx[ec]=hd[x];hd[x]=ec;ez[ec]=z;}
V cconn(I x,I y,I z){conn(x,y,z);conn(y,x,z);}
#define go(x) for(I _i=hd[(x)],y,z;y=ey[_i],z=ez[_i],_i;_i=nx[_i])
struct ms{I mx,sc;
	ms(I a=-inf,I b=-inf){mx=a;sc=b;}
	V operator +=(const ms&a){I A[4]={a.mx,mx,a.sc,sc};
		sort(A,A+4);mx=A[3];sc=(A[2]==mx?(A[1]==mx?(A[0]==mx?-inf:A[0]):A[1]):A[2]);}}dp[N][19];
struct ed{I x,y,z;}e[M];
I fa[N],n,m;
V resv(){fo(i,1,n)fa[i]=i;}
I getf(I x){return x==fa[x]?x:fa[x]=getf(fa[x]);}
bool mrg(I x,I y){return getf(x)==getf(y)?0:(fa[getf(x)]=getf(y),1);}
I f[N][19],d[N]={0,1};
V dfs(I x,I fa,I faz){
	f[x][0]=fa;dp[x][0]+=ms(faz,-inf);
	fo(i,1,18)f[x][i]=f[f[x][i-1]][i-1],
	dp[x][i]=dp[x][i-1],dp[x][i]+=dp[f[x][i-1]][i-1];
	go(x)if(y^fa)d[y]=d[x]+1,dfs(y,x,z);}
ms lcans(I x,I y){
	if(d[x]>d[y])swap(x,y);
	ms ansx,ansy;
	fd(i,18,0)if(d[f[y][i]]>=d[x])ansy+=dp[y][i],y=f[y][i];
	if(x==y)return ansy;
	fd(i,18,0)if(f[x][i]!=f[y][i])ansx+=dp[x][i],ansy+=dp[y][i],x=f[x][i],y=f[y][i];
	ansx+=dp[x][0];ansy+=dp[y][0];ansx+=ansy;
	return ansx;}
bitset<M>bz;
I main(){
	in(n,m);
	fo(i,1,m){in(e[i].x,e[i].y,e[i].z);}
	LL ss(0),ans(1ll<<62);
	fo(i,(resv(),sort(e+1,e+m+1,[=](ed a,ed b){return a.z<b.z;}),1),m)
		if(mrg(e[i].x,e[i].y))cconn(e[i].x,e[i].y,e[i].z),ss+=e[i].z;
		else if(e[i].x^e[i].y)bz.set(i);
	dfs(1,0,-inf);
	for(I i=bz._Find_first();i<=m;i=bz._Find_next(i)){
		ms Rans=lcans(e[i].x,e[i].y);
		assert(e[i].x<=N&&e[i].y<=N);
		if(Rans.mx!=e[i].z)ans=min(ans,ss-Rans.mx+e[i].z);
		else ans=min(ans,ss-Rans.sc+e[i].z);
		assert(Rans.mx!=Rans.sc);
	}printf("%lld\n",ans);
	return 0;}

警示后人 WA#1/2/3/6/12

讨论操作

回复

相关推荐

警示后人 WA#1/2/3/6/12