dfs

1/13ページ

06-圖1 列出連通集   (25分)

給定一個有NNN個頂點和EEE條邊的無向圖,請用DFS和BFS分別列出其所有的連通集。假設頂點從0到N−1N-1N−1編號。進行搜尋時,假設我們總是從編號最小的頂點出發,按編號遞增的順序訪問鄰接點。 輸入格式: 輸入第1行給出2個整數NNN(0<N≤100<N\le 100<N≤1 […]

CSU暑期集訓day05_DFS_單源最大權路徑

題目: 有一棵由N個結點構成的樹,每一條邊上都有其對應的權值。現在給定起點,求從該點出發的一條路徑(至少有一條邊)使得這條路徑上的權值之和最大,並輸出這個最大值。 Input 第一行一個正整數T,代表資料組數。每組資料第一行兩個正整數n(2<=n<=10^5),s(1<=s< […]

CSU暑期集訓day05_DFS_N皇后問題

題目: 在N*N的方格棋盤放置了N個皇后,使得它們不相互攻擊(即任意2個皇后不允許處在同一排,同一列,也不允許處在與棋盤邊框成45角的斜線上。  你的任務是,對於給定的N,求出有多少種合法的放置方法。 Input 共有若干行,每行一個正整數N≤10,表示棋盤和皇后的數量;如果N=0,表示結束。 Ou […]

CSU暑期集訓day06_平衡等式

題目: 寫一個程式要求當輸入在整數範圍內的一個整數R後, 計算機便會檢查,在下式□處能否填上“+”、“-”或“×”號湊成相應等式。如能湊成,則印出所有這些等式的個數。注意,考慮符號的優先順序。 1□2□3□4□5□6□7□8□9=R Input 只有一行,就是一個整數R。 Output 只有一行,就 […]

2015年第六屆藍橋杯JavaB組決賽題解——穿越雷區

標題:穿越雷區 X星的坦克戰車很奇怪,它必須交替地穿越正能量輻射區和負能量輻射區才能保持正常運轉,否則將報廢。某坦克需要從A區到B區去(A,B區本身是安全區,沒有正能量或負能量特徵),怎樣走才能路徑最短? 已知的地圖是一個方陣,上面用字母標出了A,B區,其它區都標了正號或負號分別表示正負能量輻射區。 […]