星球聯盟
題目描述 在遙遠的S星系中一共有N個星球,編號為1…N。其中的一些星球決定組成聯盟,以方便相互間的交流。 但是,組成聯盟的首要條件就是交通條件。初始時,在這N個星球間有M條太空隧道。每條太空隧道連線兩個星球,使得它們能夠相互到達。若兩個星球屬於同一個聯盟,則必須存在一條環形線路經過這兩個星球,即兩個 […]
-->
程式前沿 幫助程式設計師解決問題,增加專業技能,提升個人能力與未來世界競爭力。
題目描述 在遙遠的S星系中一共有N個星球,編號為1…N。其中的一些星球決定組成聯盟,以方便相互間的交流。 但是,組成聯盟的首要條件就是交通條件。初始時,在這N個星球間有M條太空隧道。每條太空隧道連線兩個星球,使得它們能夠相互到達。若兩個星球屬於同一個聯盟,則必須存在一條環形線路經過這兩個星球,即兩個 […]
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 […]
【題目】 題目傳送門Junk-Mail Filter Problem Description Recognizing junk mails is a tough task. The method used here consists of two steps: 1) Extract the co […]
【題目】 Description 給你一個無向圖,N(N<=500)個頂點, M(M<=5000)條邊,每條邊有一個權值Vi(Vi<30000)。給你兩個頂點S和T,求一條路徑,使得路徑上最大邊和最小邊的比值最小。如果S和T之間沒有路徑,輸出”IMPOSSIBLE”,否則輸出這個比 […]
Description 在某城市裡住著n個人,任何兩個認識的人不是朋友就是敵人,而且滿足: 1. 我朋友的朋友是我的朋友; 2. 我敵人的敵人是我的朋友; 所有是朋友的人組成一個團伙。告訴你關於這n個人的m條資訊,即某兩個人是朋友,或者某兩個人是敵人,請你編寫一個程式,計算出這個城市最多可能有多少個 […]
題目描述 在某城市裡住著 n 個人,任何兩個認識的人不是朋友就是敵人,而且滿足: 1、我朋友的朋友是我的朋友; 2、我敵人的敵人是我的朋友; 所有是朋友的人組成一個團伙。告訴你關於這 n 個人的 m 條資訊,即某兩個人是朋友,或者某兩個人是敵人,請你編寫一個程式,計算出這個城市最多可能有多少個團伙? […]
problem 給定n個人 朋友的朋友是朋友,敵人的敵人是朋友 朋友之間組成一個團伙,求團伙數 solution 將每個點x拆成兩個:x和x n(分別表示x的朋友和敵人) 如果x和y是朋友,就將x和y合併 如果x和y是敵人,就將x和y n合併,將y和x n合併 注意朋友的敵人不一定是敵人,因此如果x […]
團伙 題目背景: bzoj1370 分析:並查集,對於兩個敵人,將x與y n,y與x n,合併,然後對於朋友,將x與y合併,然後就可以符合題目要求了,敵人的敵人是朋友,朋友的朋友是朋友,注意對於朋友,x n與y n不能合併,因為沒有說朋友的敵人一定是敵人。最後統計1 ~ n中有多少集合就可以了 So […]
對於朋友,我們直接合並兩人所在的集合。對於敵人,我們分別合併一人與另一人的敵人。我們只需再記下每個人的一個敵人即可。最後統計有多少個連通塊便是答案 #include<cstdio> #include<cstring> #define N 1005 inline int rea […]
題目 noip既視感。 顯然並查集。 我們拆點,吧a拆成a與a’,如果是’F’的話,a與b連,否則,a與b’,a’與b。這樣就好了。 #include<bits/stdc .h> #define N 5000 using namespace std; int m,n,x,y; int f […]