集訓(xùn)隊(duì)作業(yè)matrix解答

1、Matrix福建省福州一中李曉瀟題目大意題目大意題目說明：搜索搜索萬能！搜索算法優(yōu)化一邊搜索，一邊計(jì)算時(shí)間復(fù)雜度： O（2N*N2）空間復(fù)雜度： O（N2）期望得分：2030深入分析想要得到一個(gè)高效算法，需要分析題目的特點(diǎn)。本題的突破口：深入分析根據(jù)矩陣乘法分配率可得：深入分析我們先對減號前面部分進(jìn)行分析；a1 a2 aN-1 aNb11 b1NbN1 bNNa1 a2 aN-1 aN*將 寫做矩陣的形式：=a1 a2 aN-1 aNb11 b1NbN1 bNNa1 a2 aN-1 aN*a1 a2 aN-1 aN=由于構(gòu)造的A矩陣是一個(gè)01矩陣，所以上式我們也可以這樣表示：深入分析我們再對減

2、號后面部分進(jìn)行分析；c1 c2 cN-1 cNa1 a2 aN-1 aN*也將 寫做矩陣的形式：深入分析根據(jù)以上的分析，我們可以知道：根據(jù)上式可知，對于ai=1,最后的D矩陣的元素值就要扣除ci ；當(dāng)ai=1且aj=1時(shí)，最后D矩陣的元素值就可以加上bij，我們的目標(biāo)是最大化D矩陣。我們發(fā)現(xiàn)問題中B矩陣十分類似用于描述圖的鄰接矩陣，因此我們聯(lián)想到可以嘗試用圖論模型來描述這個(gè)問題。深入分析 首先，對于B矩陣的元素bij是否加入答案與ai和aj 兩個(gè)元素有關(guān)，因此我們可以令其為i，j之間連邊的邊權(quán)；對于C矩陣的元素ci是否從答案中扣除只與ai有關(guān)，所以我們可以令其為點(diǎn)i的點(diǎn)權(quán)；那么A矩陣中ai為0

3、或1就可以表示最后方案中對i點(diǎn)的決策。圖論模型給出一個(gè)N個(gè)點(diǎn)的帶權(quán)無向完全圖，每個(gè)點(diǎn)的權(quán)值為pi=ci-bii,圖中點(diǎn)i和點(diǎn)j(ij)之間所連接的無向邊邊權(quán)為wij= bij +bji;要求你尋找一個(gè)子圖，使得子圖內(nèi)邊權(quán)之和減去點(diǎn)權(quán)之和最大。NOI2006 最大獲利經(jīng)典算法我們可以套用最大權(quán)閉合子圖的算法，例如下圖：312123(1,3)(1,2)(2,3)142522252-1-2-4ST252124經(jīng)典算法套用了最大點(diǎn)權(quán)閉合子圖的經(jīng)典模板，我們可以構(gòu)造出一個(gè)N 2個(gè)點(diǎn)N 2條邊的網(wǎng)絡(luò)，對于70%數(shù)據(jù)，這個(gè)算法已經(jīng)可以處理。但是注意到最大數(shù)據(jù)中N達(dá)到了600，構(gòu)造出來的網(wǎng)絡(luò)中可能會有10萬多

4、個(gè)點(diǎn)，在1s時(shí)限下，該算法明顯力不從心。時(shí)間復(fù)雜度：Maxflow(N2,N2)空間復(fù)雜度： O（N2）期望得分：6070另辟蹊徑 上面的算法之所以不能很好的解決問題，是由于沒能抓住題目的特點(diǎn)，一味的套用經(jīng)典模板，導(dǎo)致了時(shí)間效率的低下。 因此，我們需要另辟蹊徑，尋找新的構(gòu)圖方法。另辟蹊徑最大流最小割最大化最小化等于補(bǔ)集轉(zhuǎn)換對應(yīng)返回求值另辟蹊徑 令原圖為G=（V，E），選出的子圖為 G=（V，E）, 為E的補(bǔ)集。最大化最大化由于 是一個(gè)定值，所以我們的目標(biāo)變成了: 最小化：成功將問題轉(zhuǎn)化為最小化問題。另辟蹊徑將問題變成最小化問題后，我們的目標(biāo)就是構(gòu)建網(wǎng)絡(luò)，使得圖的割與取點(diǎn)方法一一對應(yīng)，通過求解最

5、小割來求最小值。我們先從簡單的情況開始考慮，假設(shè)圖中有兩個(gè)點(diǎn)A，B權(quán)值為pA ， pB;他們倆之間的無向邊權(quán)值為wAB。網(wǎng)絡(luò)構(gòu)圖 我們令最后割集中，所有i 都屬于V集合， i 都不屬于V集合。那么我們不難得到下圖：ASBTpAwAB/2wAB/2wAB/2wAB/2pB點(diǎn)A和點(diǎn)B是否屬于集合V一共有4種情況，同樣，構(gòu)建網(wǎng)絡(luò)的割也共有四種情況，它們之間一一對應(yīng)；ASBTpAwAB/2wAB/2wAB/2wAB/2pB此圖的割：A，B都屬于S集，割大小為pA+pB。對應(yīng)的方案點(diǎn)A和點(diǎn)B都屬于V, 。ASBTpAwAB/2wAB/2wAB/2wAB/2pB此圖的割：A屬于S集，B屬于T集，割大小為p

6、A+wAB。對應(yīng)的方案為僅點(diǎn)A屬于V, 。ASBTpAwAB/2wAB/2wAB/2wAB/2pBASBTpAwAB/2wAB/2wAB/2wAB/2pB此圖的割：A，B都屬于T集，割大小為wAB。對應(yīng)的方案點(diǎn)A和點(diǎn)B都不屬于V, 。此圖的割：A屬于S集，B屬于T集，割大小為pA+wAB。對應(yīng)的方案為僅點(diǎn)A屬于V, 。網(wǎng)絡(luò)構(gòu)圖更一般化的，對于N個(gè)點(diǎn)的圖，我們可以新建源匯S和T，從S向N個(gè)點(diǎn)連有向邊，連向點(diǎn)i的邊容量為 。從N個(gè)點(diǎn)向T連有向邊，點(diǎn)i連向T的邊容量為 ；圖中N個(gè)點(diǎn)，對于任意有序點(diǎn)對i和j（ij），從i向j連有向邊，容量為wij/2。網(wǎng)絡(luò)構(gòu)圖注意到在之前的討論中，我們默認(rèn)了權(quán)值為非負(fù)

7、數(shù)，但是實(shí)際上點(diǎn)權(quán)為pi有可能為負(fù)數(shù)，應(yīng)該如何處理呢?根據(jù)貪心的思想，我們權(quán)值為負(fù)數(shù)的點(diǎn)一定在最優(yōu)解中。這也是很好證明的，假如最優(yōu)解沒有選擇這個(gè)點(diǎn)，那么我們把這個(gè)點(diǎn)加入V集合， |V|的值將減小， |E|的值不會減小 ，那么最后的答案 將變得更優(yōu)。網(wǎng)絡(luò)構(gòu)圖這樣，通過求最小割就可以求出 的最小值，即我們就可以得到最大的 ，問題得到解決。當(dāng)然，即使采用了這樣的方法構(gòu)圖，圖還是很稠密的，所以，要注意網(wǎng)絡(luò)流的優(yōu)化問題，標(biāo)程采用的是Sap算法+當(dāng)前弧優(yōu)化（在稠密圖上當(dāng)前弧優(yōu)化往往效果很好），極限數(shù)據(jù)可以在0.5s以內(nèi)出解。時(shí)間復(fù)雜度：Maxflow(N,N2)空間復(fù)雜度：O（N2）期望得分：80100思

8、路總結(jié)矩陣問題搜索時(shí)間復(fù)雜度太高圖論問題經(jīng)典模型網(wǎng)絡(luò)規(guī)模太大最大化問題最小化問題最小割成功解決題目特色嚴(yán)謹(jǐn)正確題目創(chuàng)新題目難度嚴(yán)謹(jǐn)正確數(shù)據(jù)生成本題的數(shù)據(jù)規(guī)模較大，如果純隨機(jī)的生成矩陣B和C，往往會因?yàn)檫^于平均而造成矩陣A的最優(yōu)解全是0，或者全是1。筆者為了避免這種情況的出現(xiàn)，在生成數(shù)據(jù)的時(shí)候希望矩陣元素之間的差距盡量大。對于每個(gè)格子以1/5的概率生成一個(gè)很小的隨機(jī)數(shù)，以1/5的概率生成一個(gè)很大的隨機(jī)數(shù)，其他情況生成一個(gè)正常隨機(jī)值。 僅僅這樣還是不夠的，在生成數(shù)據(jù)的過程中還要考慮B，C矩陣元素值的比例與N的大小關(guān)系，隨機(jī)數(shù)的范圍，等等 為了保證數(shù)據(jù)足夠強(qiáng)，及其正確性，生成數(shù)據(jù)時(shí)筆者一共寫了8個(gè)不同的程序進(jìn)行試驗(yàn)。嚴(yán)謹(jǐn)正確語言平衡性在現(xiàn)行的制度下，參加NOI選手可以使用Pascal，C和C+三種語言，因此出題就要考慮這三種語言的公平性，這也是很容易被忽略的。為了保證公平性，筆者特意用三種語言寫了程序進(jìn)行比較，發(fā)現(xiàn)本題的讀入數(shù)據(jù)規(guī)模較大，而C和C+即使用scanf（）讀入數(shù)據(jù)的速度比Pascal慢了許多，往往因?yàn)閿?shù)據(jù)的讀入造成劣勢，對于這個(gè)問題，題目的最后特意加了個(gè)“友情提示”，給出C/C+快速讀入的方法，避免因語言造成的不公平。題目創(chuàng)新矩陣與圖論結(jié)合題目成功的用矩陣運(yùn)算來包裝圖論問題。突破傳統(tǒng)經(jīng)典算法經(jīng)典算法不能很好處理問題，需要分析問題本質(zhì)，