POJ 3107 - Godfather 树形DP..vector慎用...

网友投稿 264 2022-11-06


POJ 3107 - Godfather 树形DP..vector慎用...

提交超时..实在觉得没什么好优化的...最多改回至底而上的BFS..但好麻烦,记一堆东西..看discuss才知道主要是vector的原因..改成手写链表..500MS过,,,

选择任意一个点做树的树的root...统计每个点的子树元素个数情况..对于不是root的点..将所有点数N减去当前子树的元素个数num.作为该点的另一个孩子...

Program:

#include#include#include#include#include#include#include#include#include#define oo 1000000007#define ll long long#define pi acos(-1.0)#define MAXN 50005using namespace std; struct node{ int x,y,next;}line[MAXN*2]; int n,AnsNum,AnsData,ans[MAXN],_next[MAXN];bool used[MAXN];void addline(int x,int y,int m){ line[m].next=_next[x],_next[x]=m; line[m].x=x,line[m].y=y; return;}int dfs(int x){ int MaxSub=0,num=0,t,k; k=_next[x]; while (k) { if (!used[line[k].y]) { used[line[k].y]=true; t=dfs(line[k].y); MaxSub=max(t,MaxSub); num+=t; used[line[k].y]=false; } k=line[k].next; } MaxSub=max(MaxSub,n-(num+1)); if (MaxSub==AnsData) ans[++AnsNum]=x; else if (MaxSub

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：Go
上一篇:Uva 11825 - Hackers’ Crackdown 状态压缩DP
下一篇:在Spring 中使用@Aspect 控制自定义注解的操作
相关文章

 发表评论

暂时没有评论，来抢沙发吧~