集訓(xùn)隊(duì)作業(yè)matrix解題報(bào)告

1、Matrix 解題報(bào)福州第一中 HYPERLINK mailto:lixx1991 HYPERLINK l _TOC_250009 題目大 HYPERLINK l _TOC_250008 問(wèn)題分 HYPERLINK l _TOC_250007 算法算法算法算法 HYPERLINK l _TOC_250006 思路總 HYPERLINK l _TOC_250005 參考文 HYPERLINK l _TOC_250004 感 HYPERLINK l _TOC_250003 附 HYPERLINK l _TOC_250002 知識(shí) HYPERLINK l _TOC_250001 數(shù)據(jù)生 HYPERL

2、INK l _TOC_250000 題目大N*N B bi j 1*N 的非負(fù)矩陣C ci j 。Aai j i 一個(gè)1*N 0，1 Dd A*BC)*Ai D1*1ADD問(wèn)題分在乍看之下沒(méi)有很好想法的情況下，搜索往往就成為一種萬(wàn)能的解法。看到題目 N 20A重新計(jì)算(A*BC)*AT 2N *N2N 20的數(shù)據(jù)難以通過(guò)，N 50110114位都是相同的，可是在最后的計(jì)算的時(shí)候，我們對(duì)前綴重復(fù)每確定一位A A*B的值。E A*Bif(iN)ansmax(ans,(EC)*ATaiSEARCHaij to ejejbiSEARCHj to ejejbiO(2NN2O(N22030分我們嘗試從計(jì)算

3、矩陣 D 的公式尋找本題的突破點(diǎn)，試著對(duì)這個(gè)式子進(jìn)行化D(A*BC)*D A*B*AT C* = ( )( )( =() (2= =1 (=1 =1 (=1 = )(2=(A0，1( = (=1 = (=1 D矩陣元素值，觀察上式，發(fā)現(xiàn)當(dāng)我們將一個(gè)ai1時(shí)，ci的ai1aj 1bi j 就會(huì)加入最后的答案。我們發(fā)現(xiàn)B 矩陣十分類似用于描述圖的鄰接矩陣，因此我們聯(lián)想到可以嘗試用圖論模型來(lái)描i，jC矩陣的元素ci 是否從答案中扣除只與ai Npicibii,ij(ij)之wi j bi j bji ; NOI2006 最大獲利問(wèn)題，的確我們可以套用最大權(quán)閉 S，TS向圖中所T 連邊，容量為權(quán)值的絕

4、對(duì)值。原圖中的有 179700 個(gè)，1s 的時(shí)限該算法明顯力不從心，因此算法還需改進(jìn)。O(Maxflow(n2n2O(N26070分10萬(wàn)的級(jí)別，用點(diǎn)來(lái)代表邊的算法不能取得很好的效N 個(gè)點(diǎn)的無(wú)向完全圖，點(diǎn)ijwi j bi j bji ，點(diǎn)ipi c1i bii ，現(xiàn)在要你找出一個(gè)導(dǎo)出子圖，使得子圖內(nèi)的邊權(quán)之和減去點(diǎn)權(quán)之和的值最令原圖為 G VE) ， 我們最后選擇的子圖為 GV E) VV 的補(bǔ)集：VV VEEE EE|E V E集合和V | |(|E EV EEEV EEN 2AB，這兩個(gè)點(diǎn)的點(diǎn)權(quán)分pApBW 4EE4 V 4 V S 集合的點(diǎn)屬于V ，在割中屬于T 集合的點(diǎn)屬于V ，這樣

5、四種選：AV 且BV ，此 V W ，對(duì)應(yīng)的割如圖，割大小也為W AV BV ，此時(shí)V W pA ，對(duì)應(yīng)的割如圖，割大小也為W pAAV BV ，此時(shí)V W pB ，對(duì)應(yīng)的割如圖，割大小也為W pBEEEEAV BV ，此時(shí)EEEEV pA pB pA pBN S ，匯T ，從源S N 各連一條有向邊，與第i 個(gè)點(diǎn)連邊的容量為N 個(gè)點(diǎn)各向匯T 連一條有向邊，第i2pi N 之間相互連邊，對(duì)于i, j兩個(gè)點(diǎn)(i 定理：圖的割與V 和V wij 2EV E證明：S集合的點(diǎn)在劃分時(shí)屬于V 集合，割中屬于T 屬于V集合，那么我們就做到割與V 和V的劃分一一對(duì)應(yīng)，此時(shí)割的大小為 =1 + =1 + =

6、=1 + =1 + =1 += + +=1 =1 =1 2+ =1 + = + +=1 =1 EEV， 這樣我們就能得到最大的E E V Dpi c1,i bii V。我們可以用反證法來(lái)證明：假設(shè)在某個(gè)最優(yōu)解中，這個(gè)負(fù)權(quán)點(diǎn)不在VE點(diǎn)放入V 不可能增大，V 將會(huì)減少，最后的答案E (E V )將會(huì)變大，將E0。) sap+0.5s 以內(nèi)出解。O(Maxflow(nn2O(N280100分 = (=1 = =1 =1 = ( ) =1 =1 =1 = + + =1 =1 =1 S 匯T N S N 個(gè)點(diǎn)各連一條有向邊，向iNNbji N (i, j)(i jjij的邊的容量為bi j N個(gè)點(diǎn)向匯Ti點(diǎn)連出去的邊的容量為ci這樣我們可以將圖的割與+ O(Maxflow(nn2O(N2期望得分80100 思路總參考文感附成矩陣 B 和 C，往往會(huì)因?yàn)檫^(guò)于平均而造成矩陣 A 的最優(yōu)解全是 0，或者全是 1。筆者為了N 大小的不同而調(diào)整。B，CC矩陣代表點(diǎn)權(quán)，B矩陣代表邊權(quán)，C