首页 > 其他分享 >P4220 题解

P4220 题解

时间:2023-01-14 15:33:48浏览次数:72  
标签:cout int 题解 P4220 long ans include

前言

题目传送门!

更好的阅读体验?

思路

代码

为了使代码更容易通过,可以像我一样膜拜大佬,获得随机种子,通过的概率更大。

#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
struct G {
	struct Edge {int now, nxt; ll w;} e[N << 1];
	int head[N], cur;
	void add(int u, int v, ll w)
	{
		e[++cur].now = v, e[cur].nxt = head[u], e[cur].w = w;
		head[u] = cur;
	}
} g[3];
bool vis[N]; ll dis[3][N];
void dfs(int u, int fa, int idx) //暴力地遍历
{
	for (int i = g[idx].head[u]; i; i = g[idx].e[i].nxt)
	{
		int v = g[idx].e[i].now; ll w = g[idx].e[i].w;
		if (v == fa) continue;
		dis[idx][v] = dis[idx][u] + w, dfs(v, u, idx);
	}
}
int main()
{
	unsigned int seed = 0; //膜拜zlt的
	for (char c : "zlt is good at AK IOI") seed *= c;
	srand(seed);
	
	int n;
	scanf("%d", &n);
	for (int k = 0; k < 3; k++)
		for (int i = 1; i < n; i++)
		{
			int u, v; ll w;
			scanf("%d%d%lld", &u, &v, &w);
			g[k].add(u, v, w), g[k].add(v, u, w);
		}
	double st = clock(); ll ans = 0;
	while ("zlt txdy txdy txdy txdy") //膜拜zlt的,等同于 while(true)
	{
		int root;
		do //乱找一个没有检验过的根
		{
			root = rand() % n + 1;
			if ((clock() - st) / CLOCKS_PER_SEC >= 3.5) cout << ans, exit(0); //快超时了结束程序
		} while (vis[root]);
		
		int T = rand() % 5 + 10; //随机一个检验次数
		while (T--) //随便地暴力
		{
			if (vis[root]) break;
			vis[root] = true;
			for (int i = 0; i < 3; i++) dis[i][root] = 0, dfs(root, -114514, i);
			ll maxn = 0;
			for (int u = 1; u <= n; u++)
			{
				ll w = dis[0][u] + dis[1][u] + dis[2][u];
				if (!vis[u] && w > maxn) maxn = w, root = u;
				ans = max(ans, w);
			}
		}
	}
	cout << ans;
	return 0;
}

希望能帮助到大家!

标签:cout,int,题解,P4220,long,ans,include
From: https://www.cnblogs.com/liangbowen/p/17051904.html

相关文章

  • 【题解】P5030 长脖子鹿放置(网络流)
    长脖子鹿放置题目背景众周所知,在西洋棋中,我们有城堡、骑士、皇后、主教和长脖子鹿。题目描述如图所示,西洋棋的“长脖子鹿”,类似于中国象棋的马,但按照“目”字攻击,且没......
  • 1.14模拟赛题解
    T1考虑枚举线段的中点,计算它对答案的贡献。时间复杂度\(O(nm)\)。T2首先可以计算出最大流量\(maxf=\dfrac{sum}{len}\)。那么就可以将\(k\)条路径当成一条来看。把......
  • 【题解】P4292 [WC2010]重建计划
    【乐正绫AI】世末歌者「Cotton」绫绫,有你AI的每一天,我都很幸福[大笑][大笑][大笑]【乐正绫AI】世末歌者【砖厂浪人&TsingClouds】绫绫,有你的每一天,我都很幸福[大笑][大......
  • Centos7下安装Dogtail GUI自动化测试工具并打开sniff工具过程中遇到的问题解决方法
    (目录)因为测试需要,需在Centos下进行liunxGUI软件自动化测试,所以用到了python的Dogtail库,继而使用Dogtail的sniff控件获取工具,但是遇到了很多问题记录如下。1环境Cent......
  • SPOJ LCMSUM 题解
    LCMSUM题意:求:\(\sum\limits_{i=1}^n\lim(i,n)\)数据范围:\(1\leqT\leq3\times10^5\),\(1\leqn\leq10^6\)。原式\(=\sum\limits_{i=1}^n\frac{i\timesn}{\gc......
  • 题解 CF678D【Iterated Linear Function】
    暴力解法。初学群论,可能写的不是很严谨,望大佬指正。problem\[g^{(n)}(x)=\begin{cases}x,&(n=0).\\f(g^{(n-1)}),&(n>0).\end{cases}\]其中\(f\)是一次函数。给出......
  • 【题解】CF848C Goodbye Souvenir
    冷漠和缄默思路cdq分治。有各种懂哥写了科技做法,比如树套树和二维分块,有点离谱。首先考虑答案的形式。令\(lst_i\)为\([1,i)\)中\(a_i\)最后一次出现的位置,则......
  • AGC060 题解
    Wow,ChristmasRound.--Tom66A.NoMajority(1300)结论:若一个序列有严格众数,则序列中必有两个相同数字位置之差为\(1\)或\(2\)。证明设序列长为$k$,则严格......
  • vue 使用echarts图表 setOption多次很卡问题解决
    项目场景:在开发ISM组态软件时,使用echarts图表,拖拽图表很卡。问题描述在vue中使用echarts使用setOption更新加载图形很慢原因分析:由于this.echartsView=echarts.init(view,......
  • Ubuntu Server20.04 sssd+samba4共享无法访问问题解决
    UbuntuServer20.04sssd+samba4共享无法访问问题解决报错: \\ipisnotaccessible排查:在samba的log里(/var/log/samba/log.ip)能看到winbinddnotrunning解决:#apt-getins......