機(jī)器選擇

題目大意：

有一個(gè)樹狀的圖，要求安一個(gè)點(diǎn)，使這個(gè)點(diǎn)到最遠(yuǎn)的點(diǎn)的距離最小

原題：

題目描述

自從省隊(duì)NOI賽前集訓(xùn)在scz舉行之后，一個(gè)名叫cs1.6.exe的文件開始在機(jī)房廣泛使用起來。每天大家都要找神犇小X借移動(dòng)硬盤，考里面的這個(gè)文件。
由于機(jī)房里需要考這個(gè)文件的人太多了，每天都要花一段時(shí)間一個(gè)人一個(gè)人的去拷貝。小T覺得這實(shí)在是太麻煩了，就想找一個(gè)一勞永逸的方法。
小T調(diào)查了一下，機(jī)房有n臺(tái)機(jī)器，且有局域網(wǎng)，所有機(jī)器通過一些網(wǎng)線連接起來，其整個(gè)布局是一個(gè)樹形結(jié)構(gòu)，即任意兩臺(tái)機(jī)器間都有且僅有一條路徑。小T想在其中某一臺(tái)機(jī)器上儲(chǔ)存這個(gè)文件，需要的同學(xué)就可以直接通過局域網(wǎng)來下載這個(gè)文件。
網(wǎng)絡(luò)上信息傳輸是需要時(shí)間的，我們定義兩臺(tái)機(jī)器間數(shù)據(jù)傳輸?shù)臅r(shí)間為連接這兩臺(tái)機(jī)器的路徑所包含的網(wǎng)線數(shù)量。雖然機(jī)房里通過局域網(wǎng)傳個(gè)文件是很快的，但對(duì)于急不可耐的同學(xué)們來說，一分一秒都是寶貴的，文件傳輸越快越好。所以小T要選擇一臺(tái)機(jī)器存儲(chǔ)文件，使得所有機(jī)器下載這個(gè)文件需要的總時(shí)間（即最后一臺(tái)機(jī)器完成下載的時(shí)間）盡可能短。
現(xiàn)在，你需要給出這個(gè)最短時(shí)間，以便讓小T看看他的決策是否最優(yōu)。

輸入

第1行：一個(gè)整數(shù)n。
第2_{n行：兩個(gè)整數(shù)u、v，即u、v兩臺(tái)機(jī)器間有一條網(wǎng)線連接。機(jī)器從1}n編號(hào)。
輸入數(shù)據(jù)保證是一個(gè)連通的樹型結(jié)構(gòu)。

輸出

1行一個(gè)整數(shù)，即最短的時(shí)間。

輸入樣例

5 3 2 2 1 5 2 2 4

輸出樣例

1

說明

【數(shù)據(jù)范圍】

對(duì)于30%的數(shù)據(jù)，n≤100；
對(duì)于50%的數(shù)據(jù)，n≤1000；
對(duì)于100%的數(shù)據(jù)，2≤n≤100000。

解題思路：

直接暴力搜可以拿50分
想要拿100分就要先求出這棵樹的直徑，然后除以2就可以了

代碼：

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> using namespace std; int n,m,x,y,w,k,ans,p[100005],head[100005]; struct rec {int to,next; }a[200005]; void dfs(int dep,int s) {p[dep]=1;//記錄if (s>ans) ans=s,k=dep;//代替for (int i=head[dep];i;i=a[i].next)if (!p[a[i].to]) dfs(a[i].to,s+1);//搜下去p[dep]=0; } int main() {int size = 256 << 20;char*p=(char*)malloc(size) + size;__asm__("movl %0, %%esp\n" :: "r"(p) );//開棧scanf("%d",&n);for (int i=1;i<n;++i){scanf("%d %d",&x,&y);a[++w].to=y;//存線路a[w].next=head[x];head[x]=w;a[++w].to=x;a[w].next=head[y];head[y]=w;}dfs(1,0);ans=0;dfs(k,0);//求直徑printf("%d",(ans+1)/2);//除以2（加1是因?yàn)樗怯?開始的） }

總結(jié)

以上是生活随笔為你收集整理的【dfs】【树】机器选择的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。