ioi金牌選手何林論文：sgu219解題報(bào)告

《ioi金牌選手何林論文：sgu219解題報(bào)告》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、題目翻譯SGU219—Synchrograph題目描述在系統(tǒng)學(xué)中，Petrinets的一種特殊情況經(jīng)常被納入考慮范圍，這種特殊情況被稱為Synchrograph。Synchrograph是一個(gè)有向圖，每條弧都有一個(gè)非負(fù)整數(shù)權(quán)。一個(gè)點(diǎn)，如果所有指向它的邊都是正數(shù)(也就是大于0)，這個(gè)點(diǎn)就稱之為“可燃點(diǎn)”。對(duì)Synchrograph的操作是一輪一輪進(jìn)行的。在每一輪中，操作者都會(huì)隨機(jī)的選一個(gè)“可燃點(diǎn)”進(jìn)行“燃燒”。所謂燃燒就是：所有指向這個(gè)點(diǎn)的弧權(quán)都減1，所有從這個(gè)點(diǎn)指出去的弧都加1。每一輪之后，“可燃點(diǎn)”根據(jù)新的弧權(quán)被更新，然后下一輪操作繼續(xù)進(jìn)行。如果存在一個(gè)操作序列，使得某個(gè)點(diǎn)變成可燃點(diǎn)，那么這

2、個(gè)點(diǎn)就稱之為“潛在活動(dòng)點(diǎn)”。如果經(jīng)過(guò)任意一個(gè)操作序列之后，某個(gè)點(diǎn)依然是“潛在活動(dòng)點(diǎn)”，這個(gè)點(diǎn)就稱之為“活動(dòng)點(diǎn)”。輸入格式第一行包含兩個(gè)整數(shù)N和M，分別表示頂點(diǎn)數(shù)和弧數(shù)(1<=n<=1000,1<=m<=50000)。接下來(lái)M行每行描述一條邊。每行三個(gè)數(shù)，分別表示一條弧的起點(diǎn)、終點(diǎn)和權(quán)。所有的權(quán)都不超過(guò)109。輸出格式輸出包括n行，第i行描述第i個(gè)頂點(diǎn)。如果是活動(dòng)點(diǎn)，就輸出1，否則輸出0。樣例Input68121430240431160631320451000000000Output100001解題報(bào)告Synchrograph解題報(bào)告【題意分析】如果一個(gè)點(diǎn)無(wú)論如何也不可能再次變成可燃點(diǎn)，這個(gè)點(diǎn)就

3、叫做“冰凍點(diǎn)”。如果存在一個(gè)操作序列，可以把某個(gè)點(diǎn)變成“冰凍點(diǎn)”，那么這個(gè)點(diǎn)叫做“永久冰凍點(diǎn)”。如果無(wú)論如何也無(wú)法把一個(gè)點(diǎn)變成“冰凍點(diǎn)”，這個(gè)點(diǎn)就是活動(dòng)點(diǎn)。題目要求的就是輸出哪些是活動(dòng)點(diǎn)、哪些是永久冰凍點(diǎn)。【關(guān)于一些特殊情況的分析】首先考慮一個(gè)連通的有向無(wú)環(huán)圖。圖中肯定有入度為0的點(diǎn)，這樣的點(diǎn)可以看作一個(gè)“發(fā)動(dòng)機(jī)”。因?yàn)檫@種點(diǎn)永遠(yuǎn)是可燃點(diǎn)，通過(guò)它可以源源不斷的給其他的點(diǎn)輸送權(quán)值，所以叫做“發(fā)動(dòng)機(jī)”。對(duì)于任意一個(gè)點(diǎn)，總能找到一條從某個(gè)“發(fā)動(dòng)機(jī)”到它的路徑，對(duì)路徑上的點(diǎn)依次燃燒即可。所以圖中的每個(gè)點(diǎn)都是活動(dòng)點(diǎn)。然后考慮一個(gè)圈。設(shè)這個(gè)圈是a1,a2,…,ak。如果圈里的每條弧都是0，那么這k個(gè)點(diǎn)都是

4、永久冰凍點(diǎn)。因?yàn)槿ν獾狞c(diǎn)燃燒，對(duì)于圈中的弧沒(méi)有任何影響，而圈中的點(diǎn)至少有一條圈中的0弧將其“凍”住。所以永遠(yuǎn)也不能打破這個(gè)冰凍的狀態(tài)。【關(guān)于一般性性質(zhì)的分析】上面對(duì)題目有了一個(gè)感性的認(rèn)識(shí)，我們來(lái)進(jìn)一步分性一般性分析。性質(zhì)1永久冰凍點(diǎn)的后繼也是永久冰凍點(diǎn)。證明設(shè)v是永久凍結(jié)點(diǎn)，v的后繼是u。因?yàn)関是永久凍結(jié)點(diǎn)，根據(jù)定義，存在一個(gè)序列A，把v變成凍結(jié)點(diǎn)。執(zhí)行A后v永遠(yuǎn)不可能燃燒了。注意這條邊。因?yàn)関不可能再燃燒，所以永遠(yuǎn)不可能增加。如果此時(shí)的u不是凍結(jié)點(diǎn)，那么就必然存在序列使得u燃燒；燃燒之后如果還沒(méi)凍結(jié)，那么就繼續(xù)燃燒……如此燃燒下去。因?yàn)槊看稳紵?v,u>都至少減少1，不可

5、能增加；同時(shí)是有限的，所以經(jīng)過(guò)若干次操作后，v就不可能再操作了。所以u(píng)肯定也是永久凍結(jié)點(diǎn)。證畢。零圈肯定是永久凍結(jié)電，然后其后繼也可以確定為永久凍結(jié)點(diǎn)。通過(guò)性質(zhì)1，我們把很大一部分確定為“永久冰凍點(diǎn)”了?？梢园堰@些點(diǎn)從圖中刪除了（因?yàn)樗麄儾恢赶蛉魏畏怯谰帽鶅鳇c(diǎn)，對(duì)他們進(jìn)行操作是不可能也沒(méi)有必要的）。下面的討論中，圖中不再存在弧全部為零的圈。性質(zhì)2如果一個(gè)點(diǎn)的前趨全部是活動(dòng)點(diǎn)，那么這個(gè)點(diǎn)就是活動(dòng)點(diǎn)。證明設(shè)點(diǎn)v的前趨是u1,u2,…,uk。對(duì)于u1，因?yàn)槭腔顒?dòng)點(diǎn)，所以存在序列A1，燃燒u1。如果A1中本身包含了v，那么v就是活動(dòng)點(diǎn)。否則通過(guò)A1至少在原來(lái)的基礎(chǔ)上增加1。對(duì)于u

6、2，因?yàn)槭腔顒?dòng)點(diǎn)，所以存在序列A2，燃燒u2。如果A2中本身包含了v，那么v就是活動(dòng)點(diǎn)。否則通過(guò)A2至少在原來(lái)的基礎(chǔ)上增加1，并且不會(huì)減少?！瓕?duì)于uk，因?yàn)槭腔顒?dòng)點(diǎn)，所以存在序列Ak，燃燒uk。如果Ak中本身包含了v，那么v就是活動(dòng)點(diǎn)。否則通過(guò)Ak至少在原來(lái)的基礎(chǔ)上增加1，并且,,……,都不會(huì)減少。最后,,……,都是非0的數(shù)，所以可以燃燒v了。綜上，v肯定可以通過(guò)一系列的操作后而燃燒，所以v是活動(dòng)點(diǎn)。證畢。入度為0的點(diǎn)肯定是活動(dòng)點(diǎn)，通過(guò)性質(zhì)2，圖中很大一部分點(diǎn)已經(jīng)確定為活動(dòng)點(diǎn)了。但

7、是還有一部分點(diǎn)無(wú)法確定。如下圖：5001紅色的點(diǎn)是活動(dòng)點(diǎn)，其它的點(diǎn)都無(wú)法根據(jù)性質(zhì)2確定了?，F(xiàn)在仍然無(wú)法確定屬性的點(diǎn)就是非零圈（即圈中的弧不全為0）。性質(zhì)3非零圈永遠(yuǎn)不可能變成全零圈。證明燃燒圈外的點(diǎn)對(duì)圈內(nèi)的弧沒(méi)有影響。如果燃燒圈內(nèi)點(diǎn)，那么就有一條圈內(nèi)弧減1、一條圈內(nèi)弧加1。所以圈中的總權(quán)和始終保持不變。因此不可能變成全零圈。證畢。性質(zhì)4非零圈中的點(diǎn)必然不是永久凍結(jié)點(diǎn)（也就是說(shuō)必然是活動(dòng)點(diǎn)）。關(guān)于這