【消息傳遞】解題報告

3.消息傳遞

【問題描述】

巴蜀國的社會等級森嚴，除了國王之外，每個人均有且隻有一個直接上級，當然國王沒有上級。如果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的人直接上級的編号。

【檔案輸出】

檔案輸出共計兩行：

第一行為一個整數，表示最後一個人接到消息的最早時間。

第二行有若幹個數，表示可供選擇人的編号，按照編号從小到大的順序輸出，中間用空格分開。

【樣例輸入】

8

1

1

3

4

4

4

3

【樣例輸出】

5

3 4 5 6 7

感覺很基礎的一道題，但是沒敢下手，就是卡在了一個點上，父親傳遞給兒子的時候（枚舉每一個點為根節點），每一個的時間是不同的，當時卡在了這一點上，沒有想出解決方案。實際上隻需要一個貪心就夠了，也就是盡早給時間比較久的傳遞，是以（覃禹舜的選排）按降序排序就好了，f[i] = max{f[j]+k}j是i的兒子，k為排序的序号。

一開始的時候考慮的是，求一條直徑，在直徑上找點，但是仔細看題，給每個兒子傳遞的時間是不同的，是以用前序的搜尋是無法解決的，因為傳遞給兒子的順序是要由兒子的時間來決定的，是以這個政策是錯誤的。從這裡啟發寫樹形DP。

這道題再次使用到歐教講過多次的技巧。一棵形狀不确定的樹，不用建出來，隻需要在搜尋的時候用标記變量記錄走過的點，即能實作動态地建一棵樹。這道題同樣，因為從一個點出發，必須走遍其他所有的點（這一點不同于前兩天那一道treedp，因為那一道題可以選擇不走某一棵子樹，是以一次dp就行了，在路上維護ans值），是以必須進行n次dp，每次以i為根，解為f[i]。

讨論了這些這些之後，就沒有多少技巧性的東西，就是一個簡單的treedp。

就是卡在了

qsort(s[l]+1,s[l][0],sizeof(s[1][0]),&bigger);

for (long i=1;i<s[l][0]+1;i++)

{

f[l] >?= s[l][i]+i;

}

這部分上。

有什麼啟示呢？有什麼啟示呢？我遇到瓶頸了。。。感覺這種時候反而更需要打開思維才行啊，局限了。而且有時候就隻是一個很小的跳躍而已。

/AC

#include <cstdio>
#include <cstdlib>
struct node
{
	long index;
	node* next;
};


node* peo[1002];
long n;
const long oo = 0x7fff0000;
long s[1002][1002];
long f[1002];
bool used[1002];


int bigger(const void* a,const void* b)
{
	long aa = *(long*)a;
	long bb = *(long*)b;
	
	if (aa>bb) return -1;
	if (aa<bb) return 1;
	return 0;
}


void dfs(long l)
{
	if (f[l]>-oo) return;
	node* ths = peo[l];
	while (ths)
	{
		if (!used[ths->index])
		{
			used[ths->index] = true;
			dfs(ths->index);
			s[l][++s[l][0]] = f[ths->index];
			used[ths->index] = false;
		}
		ths = ths->next;
	}
	if (s[l][0]==0)
	{
		f[l] = 0;
		return;
	}
	qsort(s[l]+1,s[l][0],sizeof(s[1][0]),&bigger);
	for (long i=1;i<s[l][0]+1;i++)
	{
		f[l] >?= s[l][i]+i;
	}
}


void insert(long a,long b)
{
	node* tmp = new node;
	tmp->index = b;
	tmp->next = peo[a];
	peo[a] = tmp;
}


long fangan[1002];


int main()
{
	freopen("news.in","r",stdin);
	freopen("news.out","w",stdout);
	scanf("%ld",&n);
 	for (long i=2;i<n+1;i++)
	{
		long a;
		scanf("%ld",&a);
		insert(a,i);
		insert(i,a);
	}
	long ans = oo;
	for (long i=1;i<n+1;i++)
	{
		for (long j=1;j<n+1;j++)
		{
			f[j] = -oo;
			s[j][0] = 0;
		}
		used[i] = true;
		dfs(i);
		used[i] = false;
		if (ans>f[i])
		{
			ans = f[i];
			fangan[0] = 1;
			fangan[1] = i;
		}
		else if (ans==f[i])
		{
			fangan[++fangan[0]] = i;
		}
	}
	printf("%ld\n",ans+1);
	for (long i=1;i<fangan[0]+1;i++)
		printf("%ld ",fangan[i]);
}
           

覃禹舜，節約空間，選擇排序

program news;
type pnode=^node;
     node=record
           data:longint;
           next:pnode;
          end;
var
 mark:array[0..1001] of boolean;
 a,f,time:array[0..1001] of longint;
 p:array[0..1001] of pnode;
 max,len1,len2,t1,ans,n:longint;


procedure init;
begin
 assign(input,'news.in');reset(input);
 assign(output,'news.out');rewrite(output);
end;


procedure insert(x,y:longint);
var
 point:pnode;
begin
 new(point);
 point^.data:=y;
 point^.next:=p[x];
 p[x]:=point;
end;


procedure readdata;
var
 i,x:longint;
begin
 fillchar(p,sizeof(p),0);
 read(n);
 for i:=2 to n do
  begin
   read(x);
   insert(x,i); insert(i,x);
  end;
end;


function work(x,last:longint):longint;
var
 y:pnode;
 flag:boolean;
begin
 y:=p[x]; flag:=false;
 while y<>nil do
  begin
   if y^.data<>last then
    begin
     flag:=true;
     work(y^.data,x);
    end;
   y:=y^.next;
  end;
 if not flag then begin f[x]:=0; exit; end;
 y:=p[x];
 a[0]:=0;
 while y<>nil do
  begin
   if y^.data<>last then begin inc(a[0]); a[a[0]]:=f[y^.data] end;
   y:=y^.next;
  end;
 for len1:=2 to a[0] do
  for len2:=1 to len1-1 do
   if a[len2]<a[len1] then begin t1:=a[len2]; a[len2]:=a[len1]; a[len1]:=t1; end;
 for len1:=1 to a[0] do inc(a[len1],len1);
 max:=0;
 for len1:=1 to a[0] do
  if a[len1]>max then max:=a[len1];
 f[x]:=max;
end;


procedure main;
var
 i:longint;
begin
 for i:=1 to n do
  begin
   work(i,0);
   time[i]:=f[i];
  end;
 ans:=maxlongint;
 for i:=1 to n do if time[i]<ans then ans:=time[i];
 writeln(ans+1);
 for i:=1 to n do
  if time[i]=ans then write(i,' ');
end;


procedure terminate;
begin
 close(input);close(output);
 halt;
end;


begin
 init;
 readdata;
 main;
 terminate;
end.