欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  php教程

POJ 3107

程序员文章站 2022-04-12 09:30:54
...
提交超时..实在觉得没什么好优化的...最多改回至底而上的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 50005
using 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
相关标签： POJ 3107 Godfather 树型 DP..vector 慎用 ... 提交 超时 实在 觉得 没什么 好 优化

上一篇： alert()、confirm()和prompt()的区别与用法

下一篇： AngularJS初始化静态模板详解_AngularJS

推荐阅读