並查集

1/10ページ

2018.08.07
b612星球, bfs, html5星球, LCA, 並查集,

星球聯盟

題目描述在遙遠的S星系中一共有N個星球，編號為1…N。其中的一些星球決定組成聯盟，以方便相互間的交流。但是，組成聯盟的首要條件就是交通條件。初始時，在這N個星球間有M條太空隧道。每條太空隧道連線兩個星球，使得它們能夠相互到達。若兩個星球屬於同一個聯盟，則必須存在一條環形線路經過這兩個星球，即兩個 […]

程式語言

2018.08.05
pta, 並查集,

05-樹8 File Transfer (25分)

We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another […]

程式語言

2018.08.01
HDU, hdu括號匹配, hdu揹包問題, hdu最大子段和, hdu減支,

【HDU 2473】Junk-Mail Filter

【題目】題目傳送門Junk-Mail Filter Problem Description Recognizing junk mails is a tough task. The method used here consists of two steps: 1) Extract the co […]

程式語言

2018.08.01
bzoj, bzoj插值, 並查集, 傳遞閉包bzoj, 凸優化bzoj,

【BZOJ 1050】旅行comf

【題目】 Description 給你一個無向圖，N(N<=500)個頂點, M(M<=5000)條邊，每條邊有一個權值Vi(Vi<30000)。給你兩個頂點S和T，求一條路徑，使得路徑上最大邊和最小邊的比值最小。如果S和T之間沒有路徑，輸出”IMPOSSIBLE”，否則輸出這個比 […]

程式語言

2018.08.01
並查集,

[Baltic2003]gang團伙

Description 在某城市裡住著n個人，任何兩個認識的人不是朋友就是敵人，而且滿足： 1. 我朋友的朋友是我的朋友； 2. 我敵人的敵人是我的朋友；所有是朋友的人組成一個團伙。告訴你關於這n個人的m條資訊，即某兩個人是朋友，或者某兩個人是敵人，請你編寫一個程式，計算出這個城市最多可能有多少個 […]

程式語言

2018.08.01
bzoj, 並查集,

bzoj1370 團伙【並查集】

題目描述在某城市裡住著 n 個人，任何兩個認識的人不是朋友就是敵人，而且滿足： 1、我朋友的朋友是我的朋友； 2、我敵人的敵人是我的朋友；所有是朋友的人組成一個團伙。告訴你關於這 n 個人的 m 條資訊，即某兩個人是朋友，或者某兩個人是敵人，請你編寫一個程式，計算出這個城市最多可能有多少個團伙？ […]

程式語言

2018.08.01
並查集,

【Baltic2003】【BZOJ1370】Gang團伙（並查集，拆點）

problem 給定n個人朋友的朋友是朋友，敵人的敵人是朋友朋友之間組成一個團伙，求團伙數 solution 將每個點x拆成兩個：x和x n（分別表示x的朋友和敵人）如果x和y是朋友，就將x和y合併如果x和y是敵人，就將x和y n合併，將y和x n合併注意朋友的敵人不一定是敵人，因此如果x […]

程式語言

2018.08.01
bzoj, bzoj刷題記錄, noi, NOIP解題報告, 並查集,

bzoj1370 團伙

團伙題目背景： bzoj1370 分析：並查集，對於兩個敵人，將x與y n，y與x n，合併，然後對於朋友，將x與y合併，然後就可以符合題目要求了，敵人的敵人是朋友，朋友的朋友是朋友，注意對於朋友，x n與y n不能合併，因為沒有說朋友的敵人一定是敵人。最後統計1 ~ n中有多少集合就可以了 So […]

程式語言