消息传递树形DP

非常妙的树形DP：由于n很小，我们可以枚举每一个点作为第一个节点，计算其时间花费

那么问题就转化为对于给点节点求花费时间。

通过观察，显然我们会发现先传给花费时间多的人更加合算，因为这样可以最大限度的避免

一个人还在辛苦的传递信息，另一个人却悠闲的喝下午茶（雾）的局面

所以我们可以每次都记录下对于一个节点而言，它的所有子节点的时长，

并对其排序，排序后先传给耗时最多的人，但这样传递了之后，由于耗时最多的人最先被传递，

那么这个本应耗时最多的人就不一定还是耗时最多的人了，因此我们要分别计算所有子节点

的耗时，并取max计入ans，最后dp数组即代表一旦这个节点得知消息，要多久才可以把消息传给所有其他的人（除了传给它的那个人）,即完成任务。树的结构保证了其正确性

why是ans=min(son[i]+cnt-i+1)?

因为这里为了方便是从小到大排序，又因为是优先大的

cnt-i即为还有多少个才能到它，然后+1是因为高斯这个点信息需要1的时间。

son[i]则是加上自身的时间

 #include<bits/stdc++.h>

 using namespace std;

 #define AC 1100

 #define ACway 2500

 #define R register int

 #define D printf("line in %d\n",__LINE__);

 int n;

 int Head[AC],Next[ACway],date[ACway],tot;

 int ans[AC],minn=INT_MAX,f[AC];//use用来存储每个节点的儿子(DFS中临时存储)

 inline int read()

 {

     int x=;char c;

     while(isspace(c=getchar()));

     while(c>='' && c<='')x=x*+c-'',c=getchar();

     return x;

 }

 inline void add(int f,int w)

 {

     date[++tot]=w , Next[tot]=Head[f] , Head[f]=tot;

     date[++tot]=f , Next[tot]=Head[w] , Head[w]=tot;

 }   

 void upmax(int &a,int b)

 {

     if(b>a)a=b;

 }

 void upmin(int &a,int b)

 {

     if(b<a)a=b;

 }

 void DFS(int x,int fa)

 {

     R now;

     int cnt=,son[AC];//开在DFS里面更加方便？

     for(R i=Head[x]; i ;i=Next[i])//枚举子节点

     {

         now=date[i];

         if(now!=fa)//如果不是父亲，即为儿子

         {

             DFS(now,x);

             son[++cnt]=f[now];

         }

     }

     sort(son+,son+cnt+);

     for(R i=;i<=cnt;i++) upmax(f[x],son[i]+cnt-i+);

 }

 void pre()

 {

     R a;

     n=read();

     for(R i=;i<=n;i++)

     {

         a=read();//读入i的上级

         add(a,i);

     }

 }

 void work()

 {

     for(R i=;i<n;i++)//枚举第一个节点

     {

         memset(f,,sizeof(f));

         DFS(i,);

         ans[i]=f[i];//ans[i]存以i为第一个节点的最小耗时

         upmin(minn,ans[i]);

     }

     printf("%d\n",minn+);//还包括告诉别人的时间

     for(R i=;i<=n;i++)

         if(ans[i]==minn) printf("%d ",i);

 }

 int main()

 {

 //  freopen("in.in","r",stdin);

     pre();

     work();

 //  fclose(stdin);

     return ;

 }

巴特西

消息传递树形DP

最新文章

热门文章

巴特西

消息传递 树形DP

最新文章

热门文章

消息传递树形DP