[WC2018]通道（乱搞，迭代）

[洛谷题面]https://www.luogu.org/problemnew/show/P4221

这个题以及[CTSC2018 暴力写挂]都有类似的乱搞做法能通过考场数据。

具体搞法就是随一个起点，找一个离他最远（按题目要求计算的贡献最大）的点，让后再令 \(now=mxpoint\) 不断迭代上述过程。

然后整个上述过程最好也要不断重复进行，直到卡满时限为止就好。

多调随机种子就好。

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

using ll=long long;

const int N=100005;

int rr()

{

	return rand()%10000*10000+rand()%10000;

}

struct node

{

	int tot,h[N],nxt[N<<1],to[N<<1];

	ll dis[N],w[N<<1];

	void addedge(int u,int v,ll _w) {

		nxt[++tot]=h[u]; h[u]=tot;

		to[tot]=v; w[tot]=_w;

		nxt[++tot]=h[v]; h[v]=tot;

		to[tot]=u; w[tot]=_w;

	}

	int sz[N],dep[N],son[N];

	int fa[N],top[N];

	void dfs(int u,int father)

	{

		sz[u]=1;

		fa[u]=father;

		for(int i=h[u],v;i;i=nxt[i])

		{

			v=to[i];

			if(v!=father)

			{

				dep[v]=dep[u]+1;

				dis[v]=dis[u]+w[i];

				dfs(v,u);

				sz[u]+=sz[v];

				if(sz[v]>sz[son[u]])son[u]=v;

			}

		}

	}

	void pul(int u,int Top)

	{

		top[u]=Top;

		if(son[u])pul(son[u],Top);

		for(int i=h[u],v;i;i=nxt[i])

		{

			v=to[i];

			if(v!=fa[u]&&v!=son[u])

				pul(v,v);

		}

	}

	int lca(int u,int v)

	{

		while(top[u]!=top[v])

		{

			if(dep[top[u]]<dep[top[v]])

				swap(u,v);

			u=fa[top[u]];

		}

		return dep[u]<dep[v]?u:v;

	}

	ll dist(int u,int v)

	{

		return dis[u]+dis[v]-dis[lca(u,v)]*2;

	}

}a[3];

int n;

ll dist(int i,int j)

{

	return a[0].dist(i,j)+a[1].dist(i,j)+a[2].dist(i,j);

}

ll ans;

int main()

{

	scanf("%d",&n);

	int x,y; ll z;

	for(int k=0;k<3;k++)

	{

		for(int i=2; i<=n; i++)

		{

			scanf("%d%d%lld",&x,&y,&z);

			a[k].addedge(x,y,z);

		}

		a[k].dfs(1,0);

		a[k].pul(1,1);

	}

	if(n <= 3000)

	{

		for(int i=1; i<=n; i++)

			for(int j=i+1; j<=n; j++)

				ans=max(ans,dist(i,j));

	}

	else

	{

		for(int k=0; k<40; k++)

		{

			int now=rr()%n+1;

			for(int i=0,j; i<5; i++)

			{

				ll mx=-1;

				for(int l=1; l<=n; l++)

				{

					ll ext=dist(now,l);

					if(ext>mx)

					{

						mx=ext;

						j=l;

					}

				}

				ans=max(ans,mx);

				now=j;

			}

		}

	}

	printf("%lld",ans);

	return 0;

}

巴特西

[WC2018]通道（乱搞，迭代）

最新文章

热门文章