meow

POI 19th Letters

小強尼有一個非常長的姓,他發現跟他同一個幼稚園裡也有一個叫瑪麗的人跟他有同樣長的姓氏。不只如此,他還發現他們兩個人姓氏的字母數是相同的,有同樣多個A,同樣多個B ... ,僅僅是排列順序不同而已。

某天,強尼與瑪麗在課堂中將他們的姓用字卡排出來。瑪麗決定與強尼玩一個遊戲,強尼每次可以將他姓氏中相鄰的字卡交換,強尼必須在最少的交換次數下將字卡的順序變成瑪麗的姓。

當然這個問題對一個幼稚園的小朋友來說太難了,於是強尼決定請你,幼稚園中最優秀的程式設計師,來解決這個難題。
(繼續閱讀…)

POI 19th Distance

在這個問題中,我們可以定義兩數字間的距離。令數字 或 (必須可整除),且其中 是一個質數,經過一個操作後,我們可以將 轉變成 。而兩個數字間的最短距離 ,便是最少的操作數使得 變成 。例如 。

其中對於任意正整數 , , ,函數 有著以下的性質:

自己與自己的距離為0:
距離 到 ,與距離 到 是一樣的:
滿足三角不等式:

現在給你一個 個數字的數列 ,對於每個數字 找出最小的數字 ,其中 且 是最小的。
(繼續閱讀…)

POI 18th Shift

有一串長度為 n 的數字,由 1 到 n 組成。每次可以做以下任一種操作:

1.把最後一個數字移到第一個(操作a)
2.把第三個數字移到第一個(操作b)

請你寫一個程式來排序這些數字,將他們由小排到大。
(繼續閱讀…)

POI 18th Lollipop

在 byteburg 有賣很長很長的棒棒糖,棒棒糖是由很多個長度相同的糖塊所組成的,每一塊可能是草莓或者香草兩種口味之一。其中,每一塊草莓口味的棒棒糖需要花費 2 塊錢,而香草口味的棒棒糖需要花 1 塊錢。一根棒棒糖的價錢就是其所有組成糖塊價錢的總和。

Fig. 1: 一根棒棒糖的範例,其中有3塊草莓口味以及2塊香草口味,共價值8塊錢。

Byteasar 有一根非常長的棒棒糖。他希望在棒棒糖中間取一段連續且完整的糖塊,並且價值恰好為 k 。他想知道有沒有可能。
(繼續閱讀…)

POI 17th Railways

一條鐵路包含了兩條暫存的鐵軌1,2,且這兩條鐵軌的最遠處為死路。所有火車會從軌道A進來,並且從軌道B出去。(見下圖)

A鐵軌上總共有n節車箱,分別由1編號到n。並且他們由鐵軌A進來的順序為 。這些車廂最終需要以 的順序進到鐵軌B。每次你可以將目前A鐵軌上最前面的車廂從鐵軌A移到1,2兩條暫存軌道之一,或者可以把暫存鐵軌1,2中最上面的一台車廂移到鐵軌B。 你可以假設兩條暫存鐵軌並沒有容量的限制,皆可以容納n節以上的車廂。
(繼續閱讀…)

POI 17th Intelligence Test

拜特蘭式的智力測驗(Byteotian Intelligence Test,簡稱BIT)當中有一個測驗是這樣的。首先機器會給你一串數字,接下來給出很多組詢問,每組詢問是由幾個數字組成的,請你判斷出他是不是機器給的那一串數字當中刪掉任意個數字所剩下的。

小翔很有信心的去做了BIT測驗,沒想到除了被電的滾來滾去之外還被檢測出弱智。他非常不甘心,於是決定請身為好友的你寫一個程式來幫助他作弊。
(繼續閱讀…)

POI 17th Divine Divisor

給一個整數 N,滿足 N>1,我們說一個整數 d 是 N 的 k多重divine divisor代表 dk 是 N 的因數。例如 N = 48 = 16×3,則 2 是一個 4-多重divine divisor,2,3,6是 48 的 1-多重divine divisor。
已知N = A1 × A2 × ... × An(n ≤ 600, 2 ≤ Ai ≤ 1018),求出一個最大的正整數 k,使得 N 可以被 dk 整除,其中 d 為大於等於 2 的任意正整數。問你 k 的最大值,以及當 k 最大時 d 有多少種可能。
(繼續閱讀…)

POI 16th The Search

Bytie 和 Byteen是非常要好的朋友。但是某一天,邪惡的Bitter將Byteen軟禁在一座塔裡,Bytie需要去拯救他。然而,Bitter是非常邪惡的,他希望與Bytie玩一場遊戲,若Bytie無法取得這場遊戲的勝利,Byteen將被永遠關在這座塔裡。
塔中有非常多層樓,分別由 1 標號到 n。每一次,Bytie只可以詢問Bitter「Byteen 被關在第 x 樓的上方嗎?」或者「Byteen 被關在第 x 樓的下方嗎?」兩種問題。當然,Bytie可以任意挑選他所想要的x作為詢問。而Bitter將會誠實的回答「是」或者「不是」兩種答案,但是,每當Bitter回答一次「是」,就需要花費a元,而每回答一次「不是」則需要花費b元。
每次遊戲開始前,Bitter便會決定一個數字K,代表在Bytie回答出答案的過程中總共不能花超過K元,並且,在最差的情況下也保證可以用K元之內回答出答案。請你幫助Bytie寫個程式來解決這個難題!
Communication(函式名稱已翻譯為英文)
請在程式的最前面加入以方便你和 Bitter詢問。
C/C++: #include "poslib.h"
Pascal: uses poslib;
使用以下的函式來詢問以及回答:
void Init(int *n,int *a,int *b):初始化 N,A,B的值。

int Ask(char c,int x):若 c = 'W' 代表詢問Byteen是否在被關在 x 樓上,若 c = 'N' 代表詢問Byteen是否被關在 x 樓下。
其中 x 為 1 到 N 的正整數。若函式回答為「是」,將會回傳1,反之,則回傳0。

void Answer(int x):回答Byteen在 x 樓,回答完畢程式將自動結束。
(繼續閱讀…)

POI 16th Ice Skates

Byteasar 經營一個溜冰俱樂部,這個俱樂部的每個成員都會使用俱樂部所提供的溜冰鞋。溜冰鞋的大小由 連續標號 。正常來說,每個人腳的大小都不一定相同,他們需要穿上與自己腳大小相合的溜冰鞋。不只這樣,溜冰鞋有一個尺寸差的常數 ,代表一個腳大小為 的人恰好可以穿上大小 到大小 之間的溜冰鞋。另外,需要注意的是裡面的所有人左右腳穿的溜冰鞋大小是一樣的。
這家溜冰俱樂部剛開始提供各個尺寸大小 (從1到n) 都恰好有 雙溜冰鞋。各個時間點都會有些人加入俱樂部,或者有某些人離開俱樂部。Byteasar 擔心可能某些時候會有人找不到適合自己腳大小的溜冰鞋可以穿。
我們假設最初的時候俱樂部並沒有人。Byteasar 會提供你一連串的事件,每次會有 個會員其腳尺寸為 加入或離開俱樂部。在發生一件事情以後,Byteasar 想知道是否每個人都有合適的溜冰鞋可以穿。請你寫一個程式來檢查。
(繼續閱讀…)

POI 15th Postering

在拜特堡東區的大樓皆依照著一個原則建造:每兩棟大樓相鄰,並且中間沒有任何間隔。由東往西看,這些大樓很整齊的排成一列。

拜特堡的的市長--拜特瑟決定把這些大樓的外牆貼上海報來賺取廣告收入,以減少人民的稅金壓力(天啊,真好心)。每張海報都是長方形的,它不可以超過大樓的邊緣,並且你可以假設它最大可以到無限大。

請問你最少要幾張海報才能夠把所有大樓貼滿。

Task
請你寫一個程式:

1.讀入所有大樓的形狀
2.計算最少需要幾張海報
3.並且輸出上面的答案
(繼續閱讀…)

POI 14th Queries

Queries

Byteasar 想要破解國家安全局的密碼。他目前已經找到密碼的規則,並且他希望能破解。系統每次會給出三個正整數 , 和 , 而 Byteasar 需要回答有多少個整數對 滿足下列條件:

, 代表 和 的最大公因數。
Byteasar 希望你寫個程式來幫他自動計算解答。

Task
請寫一個程式:
從標準輸入讀入數個問題
計算各個問題的解答
並將解答輸出到標準輸出
(繼續閱讀…)

POI 12th The Bus

Byte City的街道是非常有原則的,只有南北向與東西向的道路,且每條道路間相隔的距離都相同,看起來就跟無邊無際的西洋棋棋盤一樣。南北向的道路有n條,以1到n分別編號,東西向的道路有m條,以1到m分別編號,第i條南北向道路與第j條東西向道路所形成的交叉口我們以 表示,其中 , 。

在Byte City,每個交叉口都設有一個公車站牌,公車站的起始站在 ,而終點站在 ,而且公車前進終點站的過程只會開往東邊與北邊,不會刻意繞路。小明是一個公車司機,現在有個比賽是比誰能載最多的客人,在得知每個站牌有多少人的情況下,小明想知道要怎麼設計行車路線才能使得自己能載到最多的人,然後贏得比賽。

對了,你可以假設公車內部的空間能夠容納在各站牌等車的所有乘客。
(繼續閱讀…)

POI 15th Subdivision of Kingdom

Subdivision of Kingdom

Byteotia 的國王 Byteasar 將要退休了,他希望將他的土地分成兩部分,給他的兩個孩子們。當國家被分割之後,連接兩個國家之間的路需要蓋瞭望台,由於蓋瞭望台是一件花錢的事情,因此我們希望蓋的數量越少越好。
Byteotia 恰好有偶數個都市,並且用道路連接。當王國被分割以後,每個新的王國各自擁有一半的都市,每條路連接著兩個都市。若這條路連接的都市是屬於不同的國家,則需要花錢來蓋瞭望台。
請你協助 Byteasar 來決定要怎麼分王國,才能夠使得蓋瞭望台的數量盡量少。

(繼續閱讀…)

POI 13th Sophie

小Sophie想要舉辦一場生日派對,並邀請她的幼稚園同學們來參加派對。然而,某些同學之間有些小心結,例如 Mary 說他會來參加派對,但是並不想看到 Camille 和 Emily出現在派對中,因為他們兩個上禮拜拿了 Mary 的娃娃。而 Christopher 只想來和 Sophie 以及 Camille 玩,但她並不想看到其他任何人參加這派對……等等的心結存在。
Sophie 想要邀請最多的人來參加這場派對,但是為了避免糾紛,她希望邀請來的任意兩人之間都沒有心結存在。但是,若她不能邀請到至少 K 個人來參加她的派對,她就不想辦了。請你告訴她最多能邀請到多少人。

(繼續閱讀…)

Megalopolis

Byteotia在幾十年的進步中,已經成為了一個先進的國家。小明是一個年邁的郵差,看著Byteotia將一條條鄉村小路修造成高速公路,慢慢進步成一個先進國家,其中每條鄉村小路與高速公路僅連接兩個鄉鎮,使兩個鄉鎮可以互相往來。落日漸漸落下,小明不禁懷念起以前Byteotia的樣子...

從前,Byteotia有著N個鄉鎮(以1到N分別做為編號),他們由一條條的鄉村小路所連接,每個鄉鎮都可以經由一些鄉村小路走到編號為1的鄉鎮(以Bitburg稱之),且恰好也只有一種走法。

在科技進步的衝擊下,鄉村小路慢慢的被高速公路所取代,而這些事都讓小明刻骨銘心,一直記到現在。小明是一個住在Bitburg的超級郵差,所謂的超級郵差就是要幫Bitburg把信件送到其他鄉鎮去的郵差,小明記得所有他去別的鄉鎮的時間點,以及哪一條鄉村小路被修建成高速公路的時間點,但他年紀已大,只好告訴你他的回憶,並請你幫他計算出他會經過幾條鄉村小路。

(繼續閱讀…)

TIOJ 四月

TIOJ又復活了,砍掉了許多題目

OJ消失這段時間居說主機都有開著只是沒有DNS...

(繼續閱讀…)

POI 19.Festival

Link

題目

有n(n ≤ 600) 個人以及m(m ≤ 100000) 筆訊息。每筆訊息可能是:
1.(A, B):A 的秒數恰好比B 少一秒
2.(C, D):C 的秒數不比D 多
問所有人最多能有幾種不同的秒數。

(繼續閱讀…)

POI 17.Railway

Link

題目

每台火車可以從 A 月台依序移動到 1,2 兩個暫存區(兩個stack),或把暫存區中最前面的火車移到 B 月台。有n(n ≤ 100000) 台火車,從 A 月台出來的順序為A1,A2,...An,問可不可以讓進到 B 月台的順序為1,2,...,n。

(繼續閱讀…)

POI 18.Inspection

Link

題目

你要巡察 n(n ≤ 1000000) 個點,這些點之間有邊互相相連,形成一棵樹。
你希望選一個點當做中心,從這個點巡邏其他 n-1 個點,每次巡邏點有一些規定:

1.每次的拜訪為從中心走到要巡邏的點,再走回中心點
2.最後一次巡邏完點之後不需要走回中心
3.相鄰兩次巡邏的點不可以經過相同的道路

問你從每個點當中心需要最少需花費多少時間才能夠巡邏完其他的點。

(繼續閱讀…)

POI 18.Sticks

Link

題目

有 k(3 ≤ k ≤ 50) 種顏色的棒棒,共有 n(n ≤ 1000000) 支。
給你每支棒棒的長度和顏色,問你能不能找出三支顏色不同的棒棒,使得這三支棒子的端點相接之後能形成一個面積大於 0 的三角形。

(繼續閱讀…)

POI 18.Shift

Link

題目

給你長度 n(n ≤ 2000) 的數列,為一個 1 到 n 的排列。每次可以:
1.做 k 次的 a 操作:把最後一個數字拿到第一個
2.做 k 次的 b 操作:把第三個數字拿到第一個
問你有沒有辦法在 n^2 次操作之內排序完這個數列,若有,隨便輸出一組方案。

(繼續閱讀…)

POI 17.Divine Divisor

Link

題目

已知N = A1 * A2 * ... * An(n ≤ 600, 2 ≤ Ai ≤ 10^18),求出一個最大的正整數 k,使得 N 可以被 d^k 整除,其中 d 為大於等於 2 的任意正整數。問你 k 的最大值,以及當 k 最大時 d 有多少種可能。

(繼續閱讀…)

POI 18.Party

Link

題目

有 n(3 ≤ n ≤ 3000) 個人,n 為 3 的倍數。你知道這些人之間的互相認識的關係,這裡面已知至少有 n*2/3 的人兩兩互相認識。你希望找出恰好 n/3 的人,使得所有選出來的人都互相認識。

(繼續閱讀…)

POI 12.Dicing

Link

題目

有n(n ≤ 10000)個人以及m(m ≤ 10000)場遊戲。每場遊戲會有兩個人來玩,並且分出勝負。所有遊戲結束之後會選出數個贏最多場的人當冠軍。問至少要贏多少場才會有可能當冠軍。

這題怪怪的,奇怪的複雜度。

(繼續閱讀…)

POI 18.Meteors

Link

題目

給你 n 個國家以及 m 塊土地, m 塊土地形成一個環狀(1與m相連)。
第 i 塊土地屬於國家 oi。

有 k 次流星雨將依序發生,第 i 次的流星雨將會在 [li,ri] 這個區間的土地各掉落 ai 顆流星樣本。
這些國家有分別想蒐集的樣本數量,第 i 個國家想要蒐集 pi 個樣本。
輸出每個國家分別要在第幾次的流星雨下完之後才能蒐集到他們要的樣本數量。

n,m,k ≤ 300000
pi, ai ≤ 10^9

(繼續閱讀…)

POI 18.Conspiracy

Link

題目

給一張 N(N ≤ 5000)個點的圖,把它分成兩個集合,一個點集是完全圖,一個點集是獨立集。問有幾種分法。

(繼續閱讀…)

POI 15.Blockade

Link

題目

有 N(N ≤ 100000),剛開始用 M(M ≤ 500000) 條邊互相連通。
總共有 N(N-1) 個點對(有方向性),問你每破壞一個點可以使多少個點對不連通。

(繼續閱讀…)

POI 16.The Search

Link

題目

這題是互動題

Bytie的朋友Byteen被邪惡的巫師囚禁在N(N ≤ 10^9)層的大樓當中,他必須趕在Byteen還沒壞掉之前去救她!
大樓的樓層由1標號到N,每次能夠詢問「Byteen是在x樓的上面/下面嗎?」,巫師會回答是或不是兩個答案。
每次回答是需要花費A,回答不是需要花費B(A,B ≤ 10000)。
給你N,A,B,請你設計一組詢問,使得Bytie在最差的情況下花的錢最少。

有下面幾個函式可以用:

1.void inicjuj(int *n, int *a, int *b);
初始化N,A,B。

2.int pytaj(char c, int x);
詢問的函式,若c='W'代表詢問Bytie是否在x樓上。
若c='N'代表詢問Bytie是否在x樓下面。
若回傳0代表假,回傳1代表真。

3.void odpowiedz(int wynik);
回答Bytie所在的樓層,其中wynik是Bytie所在的樓層。

(繼續閱讀…)

POI 16.Arrays

Link

題目

給兩個N列M(N,M ≤ 1000)行的矩陣a,b,其中兩個矩陣中都沒有重複的數字,且
有T(T ≤ 10)個問題,每次給你a,b矩陣,問你a能不能經過
1.交換兩列
2.交換兩行
兩種動作變成b矩陣。

(繼續閱讀…)

POI 13.Sophie

Link

題目

蘇菲想要邀請很多N(N ≤ 1000000)個人中至少K(N-10 ≤ K < N)個人來他的派對,但是小朋友們很龜毛,他們之間可能存在M(M ≤ 3000000)個單向的討厭關係,若i討厭j則代表蘇菲不能同時邀請這兩個人,否則i會不滿。
邀請的人越多越好,若可以邀請到至少K人的話,請輸出最多最多可以邀請的人數以及該要邀請哪些人。
若不能的話輸出NIE。

(繼續閱讀…)

POI 16.Ticket Inspector

Link

題目

一條直線鐵路有N(N ≤ 600)個站,從第1個站開往最後1個站,給定每個第i站上車第j站下車的人數
一位查票員會在火車上查K(K ≤ 50)次票,每次查票的時間點會在火車從第i站開往第i+1站的之間。
問最多能夠查到多少「不同的人」的票,以及該在哪裡查票,若存在多組解則輸出任意解。

(繼續閱讀…)

POI 17.Intelligence Test

Link

題目

有一個長度為M(M ≤ 1000000)的序列A,和N(N ≤ 1000000)個詢問,每個詢問給一個長度 ≤ 1000000的B序列,問你B序列是不是A的子序列。
其中所有詢問的長度總和也不超過1000000。

(繼續閱讀…)

POI 17.Guilds

Link

題目

有N(N ≤ 200000)個城市用M(M ≤ 500000)條雙向道路連接,沒有自環也沒有重邊。
有K和S兩家協會要爭地,每個城市只可以建立一個據點協會K或S,或者也可以不建立(N)。

求任意一個方案使得兩個協會在每個城市都滿足
1.城市有據點
或者
2.城市與據點直接相連

或者無解輸出NIE。

(繼續閱讀…)

POI 18.Garbage

Link

題目

有N(N ≤ 100000)個點,M(M ≤ 1000000)條邊,每條邊有0,1兩種狀態,0表示乾淨,1表示髒。
有一些垃圾車要經過,每台垃圾車走的路必定是一條簡單環(除了終點以及起點以外沒有點重複走過,且環至少有3條邊),每經過一條邊,若它是乾淨的,垃圾車就會把垃圾倒在那裡;反之,若經過髒的邊則會讓它變乾淨。
政府決定讓某些邊變乾淨、不變、或者變髒囧,給你每條邊初始的狀態和最終狀態,問能不能用有限條路徑達成最終目標。

若不行,輸出NIE,若可以,輸出每台垃圾車的路徑長以及走的路徑。
走的路徑總長必需要≤5*M。

(繼續閱讀…)

POI 17.Teleportation

Link

題目

給你n個星球(n ≤ 40000)以及m條路徑(m ≤ 1000000)。
每條路徑雙向連接兩個星球之間,每次通行花費1小時。
問最多還可以再添加多少條邊,使得1與2之間最短所需要花的時間大於250分鐘(四點多小時)。

最初給的路徑裡面1到2的最短時間必定大於250分鐘,且兩點之間必定連通。

(繼續閱讀…)

POI 17.Blocks

Link

題目

看不懂原題目QQ

簡單的意思是,給你n個正整數(n ≤ 1000000)以及m個詢問(m ≤ 50)。
每次詢問給一個整數q,問平均值 ≥q 的最長連續數列能有多長。

(繼續閱讀…)

IOI 2009.Hiring

Link

題目

有 N (N ≤ 500000)個人,每個人有等級 Q_i 和每個人願意被雇用的最低薪水 S_i(S_i , Q_i ≤ 20000)。
當你雇用了數個人,你支付給他們的薪水必須是滿足他們等級的比例(薪水可以是任意有理數)。
你有W的錢(W ≤ 10000000000),問你要怎麼樣才能夠雇用最多的人,如果有多種方法,讓雇用的價錢越小越好。

(繼續閱讀…)

USACO 2011 Mar.Tree Decoration

Link

題目

一個以1為root的樹,在每個點掛禮物有不同的代價。並且,規定每個點i所形成的子樹當中,最少要有C_i個禮物。
問滿足條件的樹最少要花費多少。

(繼續閱讀…)

USACO 2009 Jan.Damage

Link

題目

有n(n ≤ 30000)個牛棚,農庄在牛棚1。剛開始有m(m ≤ 100000)條路連起所有的牛棚。
某天因為地震,某些牛棚壞掉而不能經過,但是道路都沒有損壞。
接下來會有某些牛棚回報他們的狀況,告訴你從某個牛棚是好的,但是沒辦法回到牛棚1。
請你根據回報計算最少不能夠回到農庄的牛棚數。

(繼續閱讀…)

2011 中國國家隊.Digit

Link

題目

給一個n位數A,A的各位數和是s1,A*d的各位數和是s2。
給定n,s1,s2,d,求A的最小可能。

條件:
n ≤ 100
d ≤ 9

(繼續閱讀…)

POI 14.Building Blocks

Link

題目

有n(n ≤ 100000)個方塊,由下往上疊,分別標號為1,2,3...n。方塊i有一個數字a[i]。
每次可以抽走方塊,使上面的方塊掉下來。若方塊i的a[i]與他新的位置相等,那麼就有1分的得分。
問如何使得分最多。

(繼續閱讀…)

BOI 2009.Candy Machine

題目

有n個禮物(n ≤ 100000)會掉到地上來,你必須要剛好在時間上或者提前到那個位置來接禮物。我們以S,一個一維座標來表示禮物會掉下來的位置。

每走一單位的距離需要花1的時間。給你所有禮物掉下來的時間和位置,問你最少同時需要多少個人來撿禮物,才可以拿到所有禮物。

(繼續閱讀…)

TIOJ 1687.樹上詢問 Query on a Tree II

Link

題目

給你一棵n個點的樹(n ≤ 100000),有q筆詢問(q ≤ 200000),每筆詢問你s往t的方向走k步之後會到哪裡。

(繼續閱讀…)

TIOJ 1674.新專輯

Link

題目

n ≤ 10^13,求

(繼續閱讀…)

IOI 2000.Median Strength(TIOJ 1617)

Link

題目

互動題,有n ≤ 1499個相異數字,n為奇數。每次可以詢問三個數字之中哪個數字是中間的。
要想辦法在7777次詢問之內找出哪個數字是中位數。

(繼續閱讀…)

POI 18.Lollipop

Link

題目

給你一個長度為N的序列(N ≤ 100萬),每個數字皆是1或2。給出M筆詢問(M ≤ 100萬),問你有沒有任意一段連續的序列總和為k。

(繼續閱讀…)

OIG 1.Bajtocja

Link
原文沒有英文...索性google翻譯了一下猜對題意了!

題目

給一張N個點M條邊的圖(N ≤ 7000,M ≤ 300000),問你哪一條邊有可能是最小生成樹的其中一條邊。最小生成樹不一定是唯一的。

(繼續閱讀…)

TIOJ 1721.山上的風景

Link

題目

有n頭牛排成一條線,每隻牛可以往右和往左看。
一隻牛會被第一隻身高大於或等於自己的牛給擋到視線,問你每隻牛可以看到幾隻牛。

(繼續閱讀…)

TIOJ 1710.Dynamic Tree

Link

題目

給你一個數列,要你找出 i < j < k 且 a[ i ] < a[ j ] < a[ k ] or a[ i ] > a[ j ] > a[ k ] 的個數。

(繼續閱讀…)

POJ 3013.Big Christmas Tree

Link

題目

你要種一棵聖誕樹,上面有掛裝飾品(點)。有M條邊連接著N個點中的2個點,點和邊都有自己的權重,你必須選N-1條邊來讓他變成一棵樹。

點1在最下面,每條樹邊一定是往上的,並且建造一個點的價錢是:(邊權) * (邊上面所有點的總重)。
問你要怎麼樣把所有的裝飾品擺上去能夠使花的價錢最小。

N,M ≤ 50000

(繼續閱讀…)

Pages: 1 2 Next