小勻是一個平凡無奇的高中生，一天小勻在找升學相關資料時，發現了高中升大學四大入學管道中人數最少、時間最早（考學測前就會放榜）的特殊選才--宗旨為招收具特殊才能、特殊優良行為，或逆境向上且具強烈學習熱忱者... ...之學生為主。學科成績平平的小勻有參加過APCS、台北市資訊能力競賽。因此小勻認為特殊選才是個適合自己的管道，而開始朝著這方向努力做準備。
接著寫完備審、通過初試，時間來到了青花大學資工系特殊選才面試。面試分成兩間教室，第一間教室是做自我介紹，教授會針對備審跟自我介紹問一些問題。而第二間教室是問專業問題，要從兩道演算法的題目中，選一題跟教授解釋並解題，答完之後教授會繼續延伸題目，以下是小勻在第二間面試尾聲時跟教授的對話：
「這張圖連通、無向、沒有環。」
「這種連通、無向、沒有環的圖，我們稱它為什麼？」
「額...無向無環圖？」
「是樹。」
離答出正確答案只差臨門一腳的小勻很不甘心，於是他決定出個題目考考你知不知道樹是什麼，題目如下:
有一$N \times M$個點的圖，給定兩個陣列
$S_{i,j},1 \leq i \leq N,1 \leq j < M$與$T_{i,j},1 \leq i < N,1 \leq j \leq M$，若$S_{i,j}$為$1$代表編號$i \times M + j$的點與編號$i \times M + j+1$的點有一條無向邊相連，反之若$S_{i,j}$為$0$則沒有邊。若$T_{i,j}$為$1$代表編號$i \times M + j$的點與編號$(i+1) \times M+j$的點有一條無向邊相連，反之若$T_{i,j}$為0則沒有邊。
第一行有兩個正整數$N,M$。
接下來有$N$行，每行有$M-1$個數，第$i$行第$j$個數代表$S_{i,j}$。
再接下來有$N-1$行，每行有$M$個數，第$i$行第$j$個數代表$T_{i,j}$。
測資限制
$N,M$為正整數
$N,M \leq 1000$
$S,T \in \{0,1\}$
輸出一行包含一整數，代表將整張圖變成一棵樹的最少操作數。
3 3 1 0 0 1 0 0 1 0 0 1 1 0
3
2 3 1 1 1 1 1 1 1
2
3 3 1 0 1 0 1 1 1 1 0 0 0 0
4
本題共有三組子任務，條件限制如下所示。
子題一 37%
$N,M \leq 10$
子題二 21%
給定的圖沒有環
子題三 42%
無額外限制
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||