公司門戶網(wǎng)站的設(shè)計與實(shí)現(xiàn),asp網(wǎng)頁制作教程,wordpress 問卷調(diào)查,智能建站軟件哪個好?歡迎大家訂閱我的專欄#xff1a;算法題解#xff1a;C與Python實(shí)現(xiàn)#xff01; 本專欄旨在幫助大家從基礎(chǔ)到進(jìn)階 #xff0c;逐步提升編程能力#xff0c;助力信息學(xué)競賽備戰(zhàn)#xff01; 專欄特色 1.經(jīng)典算法練習(xí)#xff1a;根據(jù)信息學(xué)競賽大綱#xff0c;精心挑選…?歡迎大家訂閱我的專欄算法題解C與Python實(shí)現(xiàn)本專欄旨在幫助大家從基礎(chǔ)到進(jìn)階 逐步提升編程能力助力信息學(xué)競賽備戰(zhàn)專欄特色1.經(jīng)典算法練習(xí)根據(jù)信息學(xué)競賽大綱精心挑選經(jīng)典算法題目提供清晰的代碼實(shí)現(xiàn)與詳細(xì)指導(dǎo)幫助您夯實(shí)算法基礎(chǔ)。2.系統(tǒng)化學(xué)習(xí)路徑按照算法類別和難度分級從基礎(chǔ)到進(jìn)階循序漸進(jìn)幫助您全面提升編程能力與算法思維。適合人群準(zhǔn)備參加藍(lán)橋杯、GESP、CSP-J、CSP-S等信息學(xué)競賽的學(xué)生希望系統(tǒng)學(xué)習(xí)C/Python編程的初學(xué)者想要提升算法與編程能力的編程愛好者附上匯總帖GESP認(rèn)證C編程真題解析 | 匯總【題目來源】洛谷P11249 [GESP202409 七級] 小楊尋寶 - 洛谷【題目描述】小楊有一棵包含n nn個節(jié)點(diǎn)的樹樹上的一些節(jié)點(diǎn)放置有寶物。小楊可以任意選擇一個節(jié)點(diǎn)作為起點(diǎn)并在樹上移動但是小楊只能經(jīng)過每條邊至多一次當(dāng)小楊經(jīng)過一條邊后這條邊就會消失。小楊每經(jīng)過一個放置有寶物的節(jié)點(diǎn)就會取得該寶物。小楊想請你幫他判斷自己能否成功取得所有寶物?！据斎搿勘绢}單個測試點(diǎn)內(nèi)有多組測試數(shù)據(jù)。輸入第一行包含一個正整數(shù)t tt代表測試用例組數(shù)。接下來是t tt組測試用例。對于每組測試用例一共n 1 n1n1行。第一行包含一個正整數(shù)n nn代表樹的節(jié)點(diǎn)數(shù)。第二行包含n nn個非負(fù)整數(shù)a 1 , a 2 , … a n a_1, a_2, dots a_na1?,a2?,…an?其中如果a i 1 a_i 1ai?1則節(jié)點(diǎn)i ii放置有寶物若a i 0 a_i 0ai?0則節(jié)點(diǎn)i ii沒有寶物。之后n ? 1 n - 1n?1行每行包含兩個正整數(shù)x i , y i x_i, y_ixi?,yi?代表存在一條連接節(jié)點(diǎn)x i x_ixi?和y i y_iyi?的邊。【輸出】對于每組測試數(shù)據(jù)如果小楊能成功取得所有寶物輸出 Yes否則輸出 No。【輸入樣例】2 5 0 1 0 1 0 1 2 1 3 3 4 3 5 5 1 1 1 1 1 1 2 1 3 3 4 3 5【輸出樣例】Yes No【算法標(biāo)簽】《洛谷 P11249 小楊尋寶》 #圖論# #GESP# #2024#【代碼詳解】#includebits/stdc.husingnamespacestd;constintN100005,MN*2;intT;// 測試用例數(shù)量intn,a[N],root;// n: 節(jié)點(diǎn)數(shù), a[i]: 節(jié)點(diǎn)i的初始值, root: 根節(jié)點(diǎn)inth[N],e[M],ne[M],idx;// 鄰接表存儲樹boolflag;// 標(biāo)志位表示當(dāng)前樹是否合法// 添加無向邊voidadd(inta,intb){e[idx]b;ne[idx]h[a];h[a]idx;}// 深度優(yōu)先搜索// u: 當(dāng)前節(jié)點(diǎn)// fa: 父節(jié)點(diǎn)voiddfs(intu,intfa){if(!flag)return;// 如果已經(jīng)發(fā)現(xiàn)不合法直接返回intres0;// 記錄子節(jié)點(diǎn)值的和// 遍歷所有子節(jié)點(diǎn)for(intih[u];i!-1;ine[i]){intje[i];// 子節(jié)點(diǎn)if(jfa)// 跳過父節(jié)點(diǎn){continue;}// 遞歸處理子節(jié)點(diǎn)dfs(j,u);// 累加子節(jié)點(diǎn)的值resa[j];}// 如果子節(jié)點(diǎn)的和不為0將當(dāng)前節(jié)點(diǎn)設(shè)為1if(res){a[u]1;}// 檢查約束條件if((urootres2)||(u!rootres1)){flag0;// 不滿足條件標(biāo)記為非法}}intmain(){cinT;// 讀取測試用例數(shù)while(T--){cinn;// 讀取節(jié)點(diǎn)數(shù)// 初始化鄰接表memset(h,-1,sizeof(h));idx0;root0;flag1;// 初始假設(shè)樹是合法的// 讀取每個節(jié)點(diǎn)的初始值for(inti1;in;i){cina[i];}// 找到值為1的節(jié)點(diǎn)作為根節(jié)點(diǎn)for(inti1;in;i){if(a[i]1){rooti;break;}}// 讀取樹的邊f(xié)or(inti1;in;i){intu,v;cinuv;add(u,v);add(v,u);}// 從根節(jié)點(diǎn)開始DFSdfs(root,0);// 輸出結(jié)果if(flag){coutYesendl;}else{coutNoendl;}}return0;}【運(yùn)行結(jié)果】2 5 0 1 0 1 0 1 2 1 3 3 4 3 5 5 1 1 1 1 1 1 2 1 3 Yes 3 4 3 5 No