week11:求樹的直徑囤采；
隨機(jī)選點(diǎn)，搜索到距離該點(diǎn)最遠(yuǎn)的一點(diǎn)惩淳，然后從該點(diǎn)出發(fā)獲得最遠(yuǎn)點(diǎn)蕉毯，兩點(diǎn)間距即為直徑；正常思路
然后看了眼大佬的代碼思犁。real服代虾。空間換時(shí)間激蹲。
每當(dāng)加入一條邊：就當(dāng)是兩條邊棉磨；
to數(shù)組存邊號(hào)對(duì)應(yīng)的終點(diǎn)，hd數(shù)組存起點(diǎn)對(duì)應(yīng)的邊號(hào)学辱，nx數(shù)組存該起點(diǎn)對(duì)應(yīng)的另一條邊乘瓤；
核心代碼非常詭異：
int cl(int u,int p){
int a=0,b=0,t;
for(int i=hd[u];i;i=nx[i])//u的每一個(gè)方向
if(to[i]!=p)//如果沒有走回起點(diǎn)
if((t=cl(to[i],u)+1)>b)//迭代取得ｕ經(jīng)過i邊的最遠(yuǎn)。（即u為折點(diǎn)）
if((b=t)>a)
t=a,a=b,b=t;//之前ｔ>b>a;現(xiàn)在ａ>b>t;
if((b+=a)>ans)ans=b;//該點(diǎn)一邊最遠(yuǎn)ａ一邊最遠(yuǎn)ｂ策泣；
return a;//經(jīng)過ｕ的最遠(yuǎn)衙傀；
}
這個(gè)代碼倒是嚴(yán)格按提示來的，ａ保留了ｕ開始最長(zhǎng)萨咕，ｂ保留了ｕ開始次長(zhǎng)统抬；返回ａ＋b;就是邏輯很難順下來啊。
看了下ｐｏｊ１８４９的報(bào)告
1849的題是這樣：ｎ個(gè)點(diǎn)危队，n-1條有權(quán)邊,從Ｓ點(diǎn)出發(fā)的兩輛車 遍歷完所有節(jié)點(diǎn)走過的路最短聪建。
由題可知不成環(huán)。那么就只有兩種情況：
１．起點(diǎn)在直徑上交掏，那么直接求樹的直徑就好
２．起點(diǎn)不在直徑上：最長(zhǎng)鏈只被遍歷一遍妆偏，其余都是兩遍
顯然１是２的特殊情形。
用ｂｆｓ吧 因?yàn)椋洌妫蠼?jīng)常用盅弛。
所以要Ｓ干嘛钱骂。叔锐。。覺得我隨機(jī)找一點(diǎn)開始太浪費(fèi)時(shí)間见秽，從起點(diǎn)開始愉烙？
用數(shù)組模擬搞過了。
不過ｂｆｓ的正規(guī)套路是ｑｕｅｕｅ啊解取。
步步為營(yíng) 一視同仁 無解方止
queue<Point> q;
q.push(start);
Point next;
while(!q.empty())//隊(duì)列不為空繼續(xù)擴(kuò)展
{
Point tmp=q.front()步责；
q.pop();
for(int i = 0; i < 8; ++i)
{
next.row = tmp.row + directR[i];
next.col = tmp..col + directC[i];
if(inmap(next) && !visited[next.row][next.col])//inmap判斷是否在地圖內(nèi)
{
next.moves = tmp.moves + 1;
if(next.row == end.row && next.col == end.col)//如果是終點(diǎn)
return next.moves;
q.push(next);//入列
visited[next.row][next.col] = true;//標(biāo)志為走過
}
}
}
