SPOJ 1825 Free tour II

2024-08-24 11:48
文章标签 ii free tour spoj 1825

本文主要是介绍SPOJ 1825 Free tour II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

论文题:

在以root为根的第 i 棵子树上,我们用G[ i ,j ]表示root的第 i 棵子树的路径上严格有 j 个黑点的路径的最长长度。用F[ i ,j ]表示在root为根的第 i 棵子树的路径上不超过 j 个黑点的路径的最长长度。
因为所有子树里包含黑点数最多的路径的包含黑点数len可以O(N)求出,我们按照每棵子树的len从小到大的顺序遍历,这样就能将G和F数组降低一维,以G[ i ]表示当前遍历的子树路径上严格有 i 个黑点的路径的最长长度,以F[ i ]表示在该子树之前所遍历的所有子树的路径上不超过 i 个黑点的路径的最长长度。
G[ i ]可以通过一次dfs求出,而F[ i ]可以在该子树遍历完以后用G[ i ]和F[ i ]的比较以及F[ i ]和F[ i - 1]的比较来更新。
而遍历顺序可以通过求出每个子树的len,然后把子树的遍历顺序按照len从小到大排序(用个结构体能很方便的解决)。
这样每层是大约O(NlogN)的复杂度,而最多只有logN层(参见点分治的复杂度),所以总复杂度大约为O(Nlog^2N)。

手残多次,各种手残。像YYN菊苣一样再写一次。

//      whn6325689
//      Mr.Phoebe
//      http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62
#define speed std::ios::sync_with_stdio(false);typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define CPY(x,y) memcpy(x,y,sizeof(x))
#define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
#define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))#define MID(x,y) (x+((y-x)>>1))
#define ls (idx<<1)
#define rs (idx<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,r
#define root 1,1,ntemplate<class T>
inline bool read(T &n)
{T x = 0, tmp = 1;char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int MAXN=200010;struct Edge
{int to,next,c;
} e[MAXN*2];
int head[MAXN],tot;int n,k,m,ans;
int w[MAXN],g[MAXN],f[MAXN],len[MAXN];
int siz[MAXN],num[MAXN],tot_size,dep[MAXN],rot;
bool vis[MAXN];struct Node
{int v,c,len;bool operator < (const Node& b) const{return len<b.len;}Node(const int v=0,const int c=0,const int len=0):v(v),c(c),len(len) {}
} s[MAXN];
void init()
{CLR(head,-1);CLR(vis,0);CLR(w,0);tot_size=n;tot=ans=rot=0;num[0]=n;
}void addedge(int u,int v,int c)
{e[tot].to=v;e[tot].next=head[u];e[tot].c=c;head[u]=tot++;
}void get_siz(int u,int fa=-1)
{siz[u]=1;int v;for(int i=head[u]; ~i; i=e[i].next){v=e[i].to;if(!vis[v] && v!=fa){get_siz(v,u);siz[u]+=siz[v];}}
}void get_root(int u,int fa=-1)
{num[u]=0;int v;for(int i=head[u]; ~i; i=e[i].next){v=e[i].to;if(!vis[v] && v!=fa){get_root(v,u);num[u]=max(num[u],siz[v]);}}num[u]=max(num[u],tot_size-siz[u]);if(num[u]<num[rot]) rot=u;
}void get_len(int u,int fa=-1)
{len[u]=w[u];int v;for(int i=head[u]; ~i; i=e[i].next){v=e[i].to;if(!vis[v] && v!=fa){get_len(v,u);len[u]=max(len[u],len[v]+w[u]);}}
}void get_G(int u,int fa,int dep,int val)
{g[dep]=max(g[dep],val);for(int i=head[u]; ~i; i=e[i].next){int v=e[i].to;if(v==fa||vis[v]) continue ;get_G(v,u,dep+w[v],val+e[i].c);}
}void dfs(int u)
{vis[u]=1;int v,cnt=0;for(int i=head[u]; ~i; i=e[i].next){v=e[i].to;if(!vis[v]){get_siz(v);tot_size=siz[v];rot=0;get_root(v);dfs(rot);}}for(int i=head[u]; ~i; i=e[i].next){v=e[i].to;if(!vis[v]){get_len(v);s[cnt++]=Node(v,e[i].c,len[v]);}}sort(s,s+cnt);int limit=k-w[u];for(int i=0; i<=s[cnt-1].len; i++)  f[i]=-INF;for(int i=0; i<cnt; i++){for(int j=0; j<=s[cnt-1].len; j++)  g[j]=-INF;get_G(s[i].v,u,w[s[i].v],s[i].c);if(i){for(int j=0; j<=s[i].len && j<=limit; j++){int tmp=min(limit-j,s[i-1].len);if(f[tmp]==-INF) continue ;ans=max(ans,f[tmp]+g[j]);}}for(int j=0; j<=s[i].len && j<=limit; j++){f[j]=max(f[j],g[j]);if(j) f[j]=max(f[j],f[j-1]);ans=max(ans,f[j]);}}vis[u]=0;
}int main()
{freopen("data.txt","r",stdin);while(read(n)&&read(k)&&read(m)){init();for(int i=0,v; i<m; i++){read(v);w[v]=1;}for(int i=0,v,u,c; i<n-1; i++){read(u),read(v),read(c);addedge(u,v,c);addedge(v,u,c);}get_siz(1);get_root(1);dfs(rot);write(ans),putchar('\n');}return 0;
}

这篇关于SPOJ 1825 Free tour II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1102401

相关文章

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

从0到1,AI我来了- (7)AI应用-ComfyUI-II(进阶)

上篇comfyUI 入门 ,了解了TA是个啥,这篇,我们通过ComfyUI 及其相关Lora 模型,生成一些更惊艳的图片。这篇主要了解这些内容:         1、哪里获取模型?         2、实践如何画一个美女?         3、附录:               1)相关SD(稳定扩散模型的组成部分)               2)模型放置目录(重要)

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

3177. 求出最长好子序列 II 题目链接 题目描述 给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标i满足 seq[i] != seq[i + 1] ,那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。 实例1: 输入:nums = [1,2,1,1,3],

代码训练营 Day26 | 47.排序II | 51. N-皇后 |

47.排序II 1.跟46题一样只不过加一个树层去重 class Solution(object):def backtracking(self,nums,path,result,used):# recursion stopif len(path) == len(nums):# collect our setresult.append(path[:])return for i in range(

代码随想录训练营day37|52. 携带研究材料,518.零钱兑换II,377. 组合总和 Ⅳ,70. 爬楼梯

52. 携带研究材料 这是一个完全背包问题,就是每个物品可以无限放。 在一维滚动数组的时候规定了遍历顺序是要从后往前的,就是因为不能多次放物体。 所以这里能多次放物体只需要把遍历顺序改改就好了 # include<iostream># include<vector>using namespace std;int main(){int n,m;cin>>n>>m;std::vector<i

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II 1.题目 1.1递增子序列 题目链接:491. 非递减子序列 - 力扣(LeetCode) 视频讲解:回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0491.%E9%80%92%E

代码随想录算法训练营Day37|完全背包问题、518.零钱兑换II、377. 组合总和 Ⅳ、70. 爬楼梯(进阶版)

完全背包问题                  和01背包最大区别就是一个物品可以重复放多次,因此遍历空间时可以从前往后。 import java.util.*;public class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt

HumanNeRF:Free-viewpoint Rendering of Moving People from Monocular Video 翻译

HumanNeRF:单目视频中运动人物的自由视点绘制 引言。我们介绍了一种自由视点渲染方法- HumanNeRF -它适用于一个给定的单眼视频ofa人类执行复杂的身体运动,例如,从YouTube的视频。我们的方法可以在任何帧暂停视频,并从任意新的摄像机视点或甚至针对该特定帧和身体姿势的完整360度摄像机路径渲染主体。这项任务特别具有挑战性,因为它需要合成身体的照片级真实感细节,如从输入视频中可能

代码随想录刷题day24丨93.复原IP地址 ,78.子集 , 90.子集II

代码随想录刷题day24丨93.复原IP地址 ,78.子集 , 90.子集II 1.题目 1.1复原IP地址 题目链接:93. 复原 IP 地址 - 力扣(LeetCode) 视频讲解:回溯算法如何分割字符串并判断是合法IP?| LeetCode:93.复原IP地址_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0093.%E5%A4%8