誰告訴我關於2010noip囚犯的事情，最好更詳細，帶上節目，謝謝

3 拘留罪犯。

型別：資料結構 - 並查詢集合（有很多方法可以做到，也可以認為是二分圖+二分答案）。

往年noip裡真的沒人，收藏被查了，這對於收藏的收藏來說，是乙個非常好的問題。

這個想法是將所有的邊緣進行排序，然後從大到小刪除每條邊一次，對於每刪除一條邊，需要將邊緣連線的兩個點分成兩個不同的集合（即兩個罪犯被隔離在不同的監獄中）。 當我們刪除一條邊時，我們發現該邊上連線的兩個點已經在同乙個類集中，那麼這條邊就無法刪除。 也就是說，最終的解決方案。

二分圖+二分法答案。

這是正確的解決方案。

首先，將怨恨值從大到小排序，將每個囚犯設定為乙個獨立的集合，並將對抗集合設定為空集合。 將怨恨值所代表的兩點按以下方式從大到小組合：如果屬於同一集合，則輸出此值，否則依次與另乙個點的相反集合合併，注意空集！

複雜度 o（m*log（m））。

不需要雙向答案！！

但如果你只是喜歡二分法答案，我建議你二分法答案 + bfs 字面圖。 複雜度 o（m*log（10， 9））。

用兩點答案+來做，然後檢查設定。

首先，對問題給出的衝突值進行排名，然後將答案所在的區間一分為二。

區間是 [l，r]，答案是 ans=（l+r）div 2。 如果答案滿意，則大於 ans 衝突值的邊可以分為兩組，這兩組中人員的衝突值小於 ans 的值。 您可以縮小答案的上限並將其分成兩半。

如果不滿足條件，即大於 ans 衝突值的邊可以分為兩組，並且兩組中的人的衝突值大於 ans 值，則可以減小下限。 當 l = r 時，答案是 ans。

那麼如何確定條件呢？ 我們可以使用檢查和查詢集來做到這一點。

將每條邊上的兩個點作為父節點，讓關係確定它們是否在同一集合中。

每次選取一條邊時，都會確定兩條邊的點之間的關係（包括將此點作為父節點的點）。

可以通過組合和查詢集合來判斷完全解決。

貪婪的選擇，使用和檢查集合來解釋連線。

檢查當前節點和父節點是否在同一集合中，集合邊緣的權重為 0 或 1。

兩種方法是檢查+貪婪或二分法染色+二分法答案。

事實上，在某些方面，這兩種方法都不過分。

並檢查樓上提到的集合 並檢查集合本身是否在最小生成樹演算法中應用於 kruscal，這相當於所需的內容（應該沒有學校在談論最小生成樹時不談論 kruscal......

二進位圖匹配不是超類，noip2008改進組第四題雙棧排序是二進位圖染色+模擬有第一次和第二次正常。

也有人認為染色二分圖並不難...... NOIP2009 還具有 Tarjan 收縮度 DP....

可以感謝你的貪婪，勾選集合，先把所有的邊排序，然後把貪婪的加到兩個集合中（用合併來勾選集合），直到有矛盾（乙個罪犯和兩個獄卒有矛盾）輸出矛盾值，如果完全分成兩組， 然後輸出 0，可以再問一次。

sol：

對於二分圖，如果乙個無向圖可以分成兩組點 ab，並且對於任何一條邊，有 x 屬於 a，y 屬於 b，x 屬於 b，y 屬於 a，那麼它被稱為二分圖，其他的都是百度圖

在這個問題中，很明顯，罪犯是點，監獄是點，兩個罪犯之間的仇恨程度是邊緣，這個問題希望我們在原始圖中剪掉一些邊，使剩下的圖是二分圖，剩餘邊的最大值更小。

如果我們已經知道答案是ans，那麼我們可以判斷ans在o（n）中是否可行，這實際上就是保持“=ans”的邊緣，然後判斷剩餘的二分圖（百度本身）。

其次，答案是單調的，這意味著如果ans是乙個可行的解，那麼“=ans也一定是可行的”，通俗地說，ans的可行性是fffffttttttttttt，那麼這個轉折點就是必修的點，兩點都沒問題（self-baidu二分答案）。

複習更多問題，尤其是過去的問題。

找出經常出現的問題的評論型別。

不。 不要想簡單的路徑。

忙了n年，終於弄出來了，我的堆疊真的很糟糕。

var temp,n,m,i,j,x,max:longint;

heap:array[0..10005]of longint;

procedure down(m,k:longint);

var tmp,kk:longint;

begintmp:=heap[k];

while (k shl 1<=m) dobegin

kk:=k shl 1;

if (kk+1<=m)and(heap[kk]>heap[kk+1]) then inc(kk);

if heap[kk]heap[k]:=heap[kk];

k:=kk;

end else break;

end;heap[k]:=tmp;

end;begin

fillchar(heap,sizeof(heap),0);

readln(n,m);

for i:=1 to n do

beginread(x);

inc(heap[1],x);

for j:=m shr 1 downto 1 do down(m,j);

end;max:=0;

for i:=1 to m do

if maxwriteln(max);

end.