1、Matrix 解題報Matrix 解題報李曉高三五1題目大問題分題目大問題分算法算法算法算法思路總參考文感附知識2題目大N*N B bi j 1*N題目大N*N B bi j 1*N 的非負矩陣C ci j 。Aai j 一個1*N 0，1 Dd A*BC)*ATi D1*1 ADD問題分算法在乍看之下沒有很好想法的情況下，搜索往往就成為一種萬能的解法。看到題目 N 20A 重新計算A*BC)*AT2N*N2N 20N 5011011 A A*B的值。令矩陣E A*B，搜索過程為代碼如下：if (i N ) ansmax(ans,(EC)*AT3aiSEARCHaifor j1 to ejej

2、aiSEARCHaifor j1 to ejejbiSEARCHj to ejejbi30%時間復雜度O(2NN2O(N2空間復雜度期望得分2030 算法DD (A*BC)*D A*B*AT C*= ) 124 2= = 2= = =1 A0，1 =1 =1 = c)12=A0，1 = =1 =1 = =1 =1 5 a ai 1aj 1bi j 就會加入最后的答案。我們發現B B矩陣的元素bij aiaji，jC 矩陣的元素ci ai iAai01iNpi ci bii ,ij(ij)wi j bi j bji NOI2006 NN 6S，TS T 2006 S，TS T 2006 1797

3、00 個，1s 時間復雜度 O(Maxflow(n2n2O(N26070 10 N 個點的無向完全圖，點ijwi j bi j bji ，點ipi c1i bii 7令原圖為 G VE) ， 我們最后選擇的子圖為 GV E) V V 的補集：V V V EEE EE|令原圖為 G VE) ， 我們最后選擇的子圖為 GV E) V V 的補集：V V V EEE EE|E V E集合和V | | EE V E V N 2AB pApB E V 4 E V 4 S 集合的點屬于V ，在割中屬于T 集合的點屬于V 擇方法剛好就與圖的四種割聯系起來（紅色的邊為割邊81AV BV ，此時E V W ，對

4、應的割如圖，割大小也為W W pA ，對應的割如圖，割大小也為1AV BV ，此時E V W ，對應的割如圖，割大小也為W W pA ，對應的割如圖，割大小也為W pA2AV BV ，此時E V W pB ，對應的割如圖，割大小也為W pB3AV BV ，此時E V 4. AV BV ，此時 pA pB pA pBE V 9N S ，匯T S N 各連一條有向邊，與第i個點連邊的容量為 N 個點各向匯T 連一條有向邊，第i2p N 之間相互連邊，對于i, j 兩個點(i jwi j i2定理：圖的割與VN S ，匯T S N 各連一條有向邊，與第i個點連邊的容量為 N 個點各向匯T 連一條有向

5、邊，第i2p N 之間相互連邊，對于i, j 兩個點(i jwi j i2定理：圖的割與V 和V E V S集合的點在劃分時屬于V 集合，割中屬于T 屬于V 集合，那么我們就做到割與V 和V 的劃分一一對應，此時割的大小為 + 22=1 =1 = + 222=1 =1 =1 = 2=1 =1 = 2=1 =1 =+ =1 =1 E V 根據以上定理， 最小割對應著就是最小的，這樣我們就能得到最大的E V ) DEpi c1,i bii V。我們可以用反證法來證明：假設在某個最優解中，這個負權點不在V ( E V ) E V 根據以上定理， 最小割對應著就是最小的，這樣我們就能得到最大的E V

6、) DEpi c1,i bii V。我們可以用反證法來證明：假設在某個最優解中，這個負權點不在V ( E V ) 點放入V E V E 0) sap+0.5s 時間復雜度 O(Maxflow(nn2O(N2空間復雜度期望得分80100 算法 = =1 = =1 = =1 =1 =1 = + =1 =1 因為 是一個定值，所以我們將問題轉化成一個最小化問題，目標最 法是相同的S 匯T N S N 個點各連一條有向邊，向iNbji N (i, j)(i jij的邊的容量為bi j jN 個點向匯T i點連出去的邊的容量為ci 這樣我們可以將圖的割與+ + 的值一一對=1 D時間復雜度 O(Maxflow(nn2O(N2空間