acm算法淺談圖論模型的建立與應(yīng)用(參考版)
2024-10-19 19:05本頁(yè)面
【正文】 。有時(shí)，我們建立了問(wèn)題的一個(gè)模型之后，可能會(huì)感到難以求解，這時(shí)，我們可能需要對(duì)模型進(jìn)行修改，轉(zhuǎn)化，或者對(duì)原型進(jìn)行更深入的分析，抽取其中較關(guān)鍵的要素，建立一個(gè)易于求解的模型。 結(jié)語(yǔ) 問(wèn)題是千變?nèi)f化的，如何建立問(wèn)題的圖論模型并沒有通用的準(zhǔn)則。這類模型的算法系數(shù)大，編程復(fù)雜度也大，在競(jìng)賽中往往作為走投無(wú)路時(shí)的 “ 候補(bǔ)算法 ” 。這一步留給讀者自己思考。不過(guò)這樣做意義不大，而且也不是本文討論的要點(diǎn)。 至此，算法已經(jīng)優(yōu)化到了一個(gè)可以接受的地步，時(shí)間復(fù)雜度僅為 O(N+(A+B+C)3)。這一步可以在線性時(shí)間內(nèi)解決。 什么樣的卡片是沒有用的呢？ 先考慮第一種能力的選?。喝绻讶靠ㄆ吹谝环N能力值從大到小排序，顯然我們應(yīng)該盡量從前面選 A張出來(lái)，由于每張卡片只能使用一次，所以有可能會(huì)和其他的兩種能力發(fā)生沖突，而沖突的卡片數(shù)最多是 B+C張，所以實(shí)際上對(duì)我們有用的卡片只是前面的 A+B+C張。 時(shí)間復(fù)雜度： O(N3) 例題 3 貪婪之島 （ ZOJ） N太大了，需要進(jìn)一步優(yōu)化！ 優(yōu)化 例題 3 貪婪之島 （ ZOJ） 本題的卡片總數(shù)有十萬(wàn)之多，而最終要選取的卡片數(shù)不超過(guò) 100張。 例題 3 貪婪之島 （ ZOJ） 構(gòu)圖 S P2 P1 P3 1 2 3 4 5 T B,0 1,0 從頂點(diǎn)ｉ (1≤i≤N) 向匯點(diǎn)引一條弧，容量為 1，費(fèi)用為 0。 例題 3 貪婪之島 （ ZOJ） 構(gòu)圖 S P2 P1 P3 1 2 3 4 5 T B,0 從源點(diǎn)分別向 P1， P2， P3引一條弧，容量分別為 A， B， C，費(fèi)用為 0。因此，更確切地說(shuō)，本題是一個(gè)最大費(fèi)用最大流模型。 網(wǎng)絡(luò)流模型中，權(quán)的類型眾多，有流量，容量，還可以有費(fèi)用。請(qǐng)計(jì)算使用哪些卡片，以及使用卡片的哪項(xiàng)能力，可以使相應(yīng)的能力值之和最大。每張卡片可以使用其中一種能力，且每張卡片只能使用一次。做這類題目，關(guān)鍵是要把題目中的約束條件表示為不等式，再把不等式轉(zhuǎn)化為圖的最短路或最長(zhǎng)路模型。 0≤S[i]S[i1]≤Wi (0≤i≤23)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1