80分求助
查看原帖
80分求助
288716
lzqy_楼主2021/7/16 19:34

也是 WA#2,10    80pt\text{WA\#2,10\;\;80pt},但是和提交记录中所有 8080 分的错误信息都不一样……

不求帮助调代码,能否Hack或者分享一些易错点,谢谢!

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=5010;
const int inf=INT_MAX;
inline int read()
{
	register int x=0;
	register char c=getchar();
	for(;!(c>='0'&&c<='9');c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}
int n,X,Y;
vector<int>v[maxn],w[maxn];
int f[maxn],p[maxn];
int k[maxn];
int sum1,sum2;
void dfs(int fa,int x,int bian)
{
	f[x]=fa,p[x]=p[fa]+bian;
	for(register int i=0;i<v[x].size();i++)
		if(v[x][i]!=fa&&(max(v[x][i],x)!=X||min(v[x][i],x)!=Y))
			dfs(x,v[x][i],w[x][i]);
}
queue<pair<int,int> >q;
int bfs(int x,int zz,int XX)
{
	register int ans=x;
	pair<int,int>t;
	if(zz==1) sum1=0;
	else sum2=0;
	k[x]=XX,q.push(make_pair(x,0));
	while(!q.empty())
	{
		t=q.front(),q.pop();
		if(zz==1&&sum1<t.second) sum1=t.second,ans=t.first;
		if(zz==2&&sum2<t.second) sum2=t.second,ans=t.first; 
		for(register int i=0;i<v[t.first].size();i++)
			if(k[v[t.first][i]]!=XX&&(max(t.first,v[t.first][i])!=X||min(t.first,v[t.first][i])!=Y))
				k[v[t.first][i]]++,
					q.push(make_pair(v[t.first][i],w[t.first][i]+t.second));
	}
	return ans;
}
int main()
{
	n=read();
	register int x,y,z,xx,yy;
	for(register int i=1;i<n;i++)
	{
		x=read(),y=read(),z=read();
		v[x].pb(y),v[y].pb(x);
		w[x].pb(z),w[y].pb(z);
	}
	x=bfs(1,1,1),y=bfs(x,1,2);
	register int Sum1,Sum2,ans=sum1;
	for(register int i=1;i<=n;i++)
		for(register int j=0;j<v[i].size();j++)
			if(i>v[i][j])
			{
				memset(k,0,sizeof(k)),X=i,Y=v[i][j],z=w[i][j];
				x=bfs(1,1,1),y=bfs(x,1,2),dfs(0,x,0);
				Sum1=Sum2=0;
				while(Sum1<sum1/2)
					Sum1+=p[y]-p[f[y]],y=f[y];
				Sum1=min(Sum1,sum1-Sum1);
				for(register int ii=1;ii<=n;ii++)
					if(!k[ii])
					{
						xx=bfs(ii,2,1),yy=bfs(xx,2,2),dfs(0,xx,0);
						while(Sum2<sum2/2)
							Sum2+=p[yy]-p[f[yy]],yy=f[yy];
						Sum2=min(Sum2,sum2-Sum2);
						break;
					}
				ans=min(ans,max(Sum1+Sum2+z,max(sum1,sum2)));
			}
	cout<<ans<<endl;
	return 0;
} 
2021/7/16 19:34
加载中...