最新章節(jié) 62.一起來(lái)做網(wǎng)站吧網(wǎng)絡(luò)營(yíng)銷有哪些
原題鏈接:
題目描述
Foxity和他的好友們相約去爬山,但是他們每個(gè)人都來(lái)到了不同的山腳下。整個(gè)山的結(jié)構(gòu)類似一棵 "樹",有很多的觀光節(jié)點(diǎn)通過一條條山道連接起來(lái)。
在圖論中,樹是一種無(wú)向圖,其中任意兩個(gè)頂點(diǎn)之間存在唯一一條路徑?;蛘哒f(shuō),只要沒有回路的連通圖就是樹。這個(gè)問題中,我們將山頂視作樹的根節(jié)點(diǎn),而山腳視為樹的葉節(jié)點(diǎn),上山的每一條路可以視作樹的一條邊。
由于上山的道路年久失修,每條道路在同一時(shí)刻只能容納一個(gè)人,而通過一條道路需要花費(fèi) 111?時(shí)間。
現(xiàn)在他們分散在各個(gè)山腳(每個(gè)山腳恰好有一個(gè)人),現(xiàn)在他們想要知道最快的情況下,從現(xiàn)在到最后一個(gè)人登上山頂總共要花費(fèi)多久的時(shí)間。
輸入描述:
第一行一個(gè)整數(shù) n(1≤n≤1000)n(1 \le n \le 1000)n(1≤n≤1000),表示總共節(jié)點(diǎn)的數(shù)量。接下來(lái) n?1n-1n?1 行,每行兩個(gè)整數(shù),分別是 xi,yi(1≤xi,yi≤n)x_i,y_i(1 \le x_i,y_i \le n)xi?,yi?(1≤xi?,yi?≤n),表示有一條路連接 xix_ixi? 號(hào)點(diǎn) 和 yiy_iyi? 號(hào)點(diǎn),其中 111 號(hào)點(diǎn)即為山頂,保證給定的圖是一棵樹。
輸出描述:
輸出一行一個(gè)數(shù),表示所有人都到齊的最少時(shí)間。
示例1
輸入
復(fù)制3 1 2 1 3
3 1 2 1 3
輸出
復(fù)制1
1
示例2
輸入
復(fù)制4 1 2 2 3 2 4
4 1 2 2 3 2 4
輸出
復(fù)制3
3
思路:
1,這個(gè)題真的沒什么思路
2,要求每次一條路只能走一人,所有人走到1節(jié)點(diǎn)的最短時(shí)間
3,這個(gè)題最難的是,單個(gè)節(jié)點(diǎn)記錄數(shù)量,dfs深度搜索,遞歸的書寫
代碼:
int num[1100];
vector<int>g[1100];
void dfs(int z,int fa){for(int i=0;i<g[z].size();++i){int y=g[z][i];if(y==fa)continue;//防止重復(fù)遍歷if(num[y]){//模擬走的過程num[z]++;num[y]--;}dfs(y,z);//遍歷子節(jié)點(diǎn)}
}
signed main(){//dfs模擬每一秒的動(dòng)作int n;cin>>n;rep(i,1,n-1){int x,y;cin>>x>>y;g[x].emplace_back(y);//無(wú)向圖g[y].emplace_back(x);}int sum=0;rep(i,2,n){if(g[i].size()==1)sum++,num[i]=1;//記錄單個(gè)節(jié)點(diǎn)的}int ans=0;while(num[1]!=sum){//模擬每一秒,在一條路上能走則走dfs(1,1);ans++;}cout<<ans<<'\n';return 0;
}