ioi金牌選手何林論文：sgu219解題報告

《ioi金牌選手何林論文：sgu219解題報告》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。

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

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

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

4、永久冰凍點。因為圈外的點燃燒，對于圈中的弧沒有任何影響，而圈中的點至少有一條圈中的0弧將其“凍”住。所以永遠也不能打破這個冰凍的狀態(tài)。【關于一般性性質的分析】上面對題目有了一個感性的認識，我們來進一步分性一般性分析。性質1永久冰凍點的后繼也是永久冰凍點。證明設v是永久凍結點，v的后繼是u。因為v是永久凍結點，根據(jù)定義，存在一個序列A，把v變成凍結點。執(zhí)行A后v永遠不可能燃燒了。注意這條邊。因為v不可能再燃燒，所以永遠不可能增加。如果此時的u不是凍結點，那么就必然存在序列使得u燃燒；燃燒之后如果還沒凍結，那么就繼續(xù)燃燒……如此燃燒下去。因為每次燃燒都至少減少1，不可

5、能增加；同時是有限的，所以經(jīng)過若干次操作后，v就不可能再操作了。所以u肯定也是永久凍結點。證畢。零圈肯定是永久凍結電，然后其后繼也可以確定為永久凍結點。通過性質1，我們把很大一部分確定為“永久冰凍點”了?？梢园堰@些點從圖中刪除了（因為他們不指向任何非永久冰凍點，對他們進行操作是不可能也沒有必要的）。下面的討論中，圖中不再存在弧全部為零的圈。性質2如果一個點的前趨全部是活動點，那么這個點就是活動點。證明設點v的前趨是u1,u2,…,uk。對于u1，因為是活動點，所以存在序列A1，燃燒u1。如果A1中本身包含了v，那么v就是活動點。否則通過A1至少在原來的基礎上增加1。對于u

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

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