luogu P2018 消息传递

P2018 消息传递

2017-09-13

题目描述

巴蜀国的社会等级森严，除了国王之外，每个人均有且只有一个直接上级，当然国王没有上级。如果A是B的上级，B是C的上级，那么A就是C的上级。绝对不会出现这样的关系：A是B的上级，B也是A的上级。

最开始的时刻是0，你要做的就是用1单位的时间把一个消息告诉某一个人，让他们自行散布消息。在任意一个时间单位中，任何一个已经接到消息的人，都可以把消息告诉他的一个直接上级或者直接下属。

现在，你想知道：

1.到底需要多长时间，消息才能传遍整个巴蜀国的所有人？

2.要使消息在传递过程中消耗的时间最短，可供选择的人有那些？

输入输出格式

输入格式：

输入文件的第一行为一个整数N（N≤1000），表示巴蜀国人的总数，假如人按照1到n编上了号码，国王的编号是1。第2行到第N行（共N-1行），每一行一个整数，第i行的整数表示编号为i的人直接上级的编号。

输出格式：

文件输出共计两行：

第一行为一个整数，表示最后一个人接到消息的最早时间。

第二行有若干个数，表示可供选择人的编号，按照编号从小到大的顺序输出，中间用空格分开。

输入输出样例

输入样例#1：

输出样例#1：

5
3 4 5 6 7


原本一看这个题,暴力找重心,然后跑树,然后经过仔细读题,发现并没有用到重心,我们只要找到一个点到树的最长的一条带边权的路径和最大的最小。
f每一个点上的边权是从1到所连边个数的全排列,(因为每一次只能传一个)所以我们贪心选取使边权的大值对应它所连点底下边权和较小的值.
每一层强行sort加权.ans统计最小

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cstring>
#define ll long long 
#define _ =read();
using namespace std;
const int maxn=1000+100;
int read(){
    int an=0,f=1;
    char ch=getchar();
    while(!('0'<=ch&&ch<='9')){if(ch=='-');ch=getchar();}
    while('0'<=ch&&ch<='9'){an=an*10+ch-'0';ch=getchar();}
    return an*f;
}
vector<int>b[maxn];
bool vis[maxn];
int wi[maxn],n;
int f[maxn],ans[maxn],mi=(int)1e9;
bool saber(int x,int y){
    return wi[x]>wi[y];
}
void dfs(int x){
    vis[x]=1;
    for(int i=0;i<b[x].size();i++){
        if(!vis[ b[x][i] ]){
            dfs(b[x][i]);
        }
    }
    sort(b[x].begin(),b[x].end(),saber);
    for(int i=0;i<b[x].size();i++){
    wi[x]=max(i+1+wi[b[x][i]],wi[x]);
    }
    vis[x]=0;
}
int main(){
    n _ 
    for(int i=2;i<=n;i++){
        int x=read();
        b[i].push_back(x);
        b[x].push_back(i);}
    for(int i=1;i<=n;i++){
        dfs(i);
        ans[i]=wi[i];
        mi=min(mi,ans[i]);
        memset(wi,0,sizeof(wi));
    }
    cout<<mi<<endl;
    for(int i=1;i<=n;i++)if(ans[i]==mi)cout<<i<<" ";
    return 0;
}

View Code

by:s_a_b_e_r

一开始同以为是找重心，然后各种不会做……

后来看题解发现思路很神奇……

因为一单位时间每人只能传给一个人，所以这个人周围的节点是依次接到信息的

于是可以给它周围的节点分配一个边权

子树越大的节点越要先传递，边权就越小

所以枚举一遍从哪个点开始向四周传信息

最后统计最小值以及方案就可以了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1009;
int cnt,p[N],n,ans=int(1e9),an[N],f[N];
bool vis[N];
struct edge{
int to,nex;
}e[N<<1];
vector<int>q[N];
bool cmp(int x,int y){return x>y;}
void add(int u,int v)
{
     ++cnt;
     e[cnt]=(edge){v,p[u]};
     p[u]=cnt;
}
void dfs(int u)
{
    for(int i=p[u];i;i=e[i].nex)
    {
      int v=e[i].to;
      if(vis[v])continue;
      vis[v]=1;
      dfs(v);
      q[u].push_back(f[v]);
    }
    sort(q[u].begin(),q[u].end(),cmp);
    for(int i=1;i<=q[u].size();++i)
      f[u]=max(f[u],q[u][i-1]+i);
}
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;++i)
    {
      int x;
      scanf("%d",&x);
      add(x,i);add(i,x);
    }
    for(int i=1;i<=n;++i)
    {
      memset(f,0,sizeof(f));
      memset(vis,0,sizeof(vis));
      for(int j=1;j<=n;++j)q[j].clear();
      vis[i]=1;
      dfs(i);
      an[i]=f[i];
      ans=min(an[i],ans);
    }
    cout<<ans+1<<endl;
    for(int i=1;i<=n;++i)
    if(an[i]==ans)cout<<i<<" ";
    return 0; 
}

消息传递

by:wypx

s:新机房太棒了

w:突然换机房……幸福来的好突然