題解/算法 {396. 矿场搭建}

題解/算法 {396. 矿场搭建}

題解/算法 {396. 矿场搭建}

@LINK: /;

性質1: 由於原圖可能不連通, 我們令Gi為他的每個連通塊, 然後單獨考慮Gi 比如他的方案有Mi個, 那麼總答案為M1*M2*M3*..;
這要怎麼證明呢? 對於當前連通塊Gi裡的點 要保證他與某個出口是連通的, 那麼這出口 肯定是Gi裡的, 而不是其他連通塊 因為他們是不連通的;

性質2: 對於一個連通無向圖, 出口一定不會設置在割點上
比如A-x-B 你把x割點給掉了, 說明A|B裡 一定有出口, 那麼你此時 把出口設置到割點x上 是浪費的; 雖然去掉的 也可能不是x 而此時 也不需要用到x這個出口;
因此 出口一定設置到(非割點上);

性質3: 假如刪除任意割點後 條件滿足(即所有點都可以找到出口), 那麼刪除任意(非割點)後 條件也滿足;
也就是說, 你需要考慮 刪除的點 是割點的情況; 因為刪除割點 意味著分裂 即圖不再連通了, 而刪除(非割點)後 圖依然是連通的; 即刪除割點 是非常嚴重的;

@DELI;

@LINK: (/?not_checkout=1&articleId=128466820)-(@LOC_2), 對於一個連通無向圖G 對餘割集進行縮點後, 所有點分為3類{ 1(>=2個葉子節點LL (連通度為1)), 2(割點CC), 3(連通度>=2的點SS)};
我們要保證的是 刪除任意一個點後 所有的點 一定 與至少1個出口 是連通的;
由性質2, 此時我們只需考慮在1|3情況 放出口; 1情況 一定需要放一個出口(他的方案為該葉子節點對應的餘割集的大小), 即每個葉子節點上放一個出口 (刪除他的割點 他自己可以自足; 如果刪除他裡面的這個出口 那麼他裡面的其他點 跟其他出口是連通的); 即此時 一定有>=2個出口 (因為葉子節點有>=2個);
根據上面的@LINK:的性質, 3情況 不需要放出口 因此你刪除一個割點 等於是分裂成了 (一個葉子節點(裡面有1個出口), 剩餘主圖(裡面有>=1個出口)), 而對於因為主圖依然是連通的 而且裡面已經有出口了, 所以 對於3情況 不需要放出口;
. 以上的分析 有一點是錯誤的, 上面的最開始的大前提錯了, 即原圖G縮點後 不一定是有{1,2,3}這種情況, 還有一種特殊情況 在@LINK:裡也說到了, 即@IF(G有割點):[ 他的情況 確實如上面講的{1:葉子節點, 2:割點...}, 即上面的分析 是建立在 G有割點的大前提下的]; @ELSE(G沒有割點):[還有這種情況 此時就不能按照分析來了, 如果G的點數為1 則放1個出口, 否則放2個出口, 這要特判];

雖然上面的G 是連通的, 但因為他的答案 要麼是1(G只有1個點) 要麼是2(G有>1個點 且沒有割點) 要麼是t1*t2*t3*...(ti為葉子餘割集的大小), 即他是一個乘法表達式, 最終答案是G1 * G2 * G3 * ... 也是乘法, 因此 你不需要將原圖 分割成每個連通分量 單獨處理, 可以直接統一處理 即得到所有割集;

long long ANS = 0; // 設置多少個出口
long long Cont = 1; // 方案
for( auto & i : ___Tarjan_CutPoint::CutSet){int cutPoints_count = 0;for( auto j : i){ if( ___Tarjan_CutPoint::Is_cutPoint[j]){ ++ cutPoints_count;}}int others = i.size() - cutPoints_count;if( cutPoints_count >= 2){ continue;}if( cutPoints_count == 0){ // 這裡要特判, 即原圖裡的某個連通塊SG裡面 沒有割點; 此時`SG==i(即當前枚舉的這個割集)`;if( i.size() == 1){++ ANS;}else{ANS += 2;Cont *= (i.size() * 1LL * (i.size() - 1) / 2);}continue;}++ ANS;Cont *= others;
}

錯誤

把所有割點去掉後, 每個餘割集裡 放一個出口;
錯誤;
對於一個割集 他裡面有>=2個割點, 那麼他所對應的(餘割集) 不需要放置割點; 比如{1-2-3-4, 2-5-3}, 割點是2,3, 你的答案是{1,5,4}為出口, 而答案是{1,4}為出口;

筆記

Suppose G G G is a CC of the target-graph (you can find that all CCs are independent, so a CC is the minimal problem-unit); and we call all points are valid if every point can reach to a Super-Point (or itself be a Super-Point).

Let’s see a wrong device, let G 1 G1 G1 be the graph after deleting all Cut-Points (and all its adjacent-edges) from G G G, now G 1 G1 G1 consists of several C C CC CCs, then set a Super-Point in every C C CC CC;
Actually, this is wrong; cuz the question is all point should be valid after deleting one-point (note that, not deleting multiple points);
It is prone that using this device which seemed very close to the answer; (e.g., ( a − b ) ( c − d ) ( b − d ) ( b − e ) ( d − e ) (a-b) (c-d) (b-d) (b-e) (d-e) (a−b)(c−d)(b−d)(b−e)(d−e), there are 3 3 3 CCs after deleting all Cut-Points b , d b,d b,d, however, you just making a , b a,b a,b be Super-Point, all point are valid whatever any point has deleted)

When facing a Cut-Point (PBCC) problem, you should follow the next steps:
+ if the target graph is unconnected, then divide it into all it C C CC CCs (cuz all C C CC CCs are independent to each other when handling Cut-Point), let G , G 1 , G 2 , . . . G, G1, G2, ... G,G1,G2,... be all of its C C CC CCs;
+ consider all P B C C PBCC PBCCs of G G G, rather than considering all C C CC CCs after deleting all Cut-Points from G G G;
+ divide G G G into two cases: (contains Cut-Point or not)
__1 If G G G has no Cut-Point, then there has only one P B C C PBCC PBCC which equals to G G G; (which means whatever you delete any one point, the remaining graph of G G G is still connected)
__2 If G G G has Cut-Points, then there has ≥ 2 geq 2 ≥2 P B C C PBCC PBCCs where every P B C C PBCC PBCC contains ≥ 2 geq 2 ≥2 points and ≥ 1 geq 1 ≥1 Cut-Points; (which means there exist a point (must be a Cut-Point) such that G G G is no longer connected when it has deleted)
____. For every P B C C PBCC PBCC, you need divide them into two cases: (Leaf: contains 1 1 1 Cut-Point) (Non-Leaf: contains ≥ 2 geq 2 ≥2 Cut-Points)

--

According to the method introduced above:
In the case 1, if G G G has only one point (cuz there has ≥ 1 geq 1 ≥1 edges and no self-loop, G 1 G1 G1 must exist (i.e., the number of points always ≥ 2 geq 2 ≥2)), then making the sole point be Super-Point; otherwise, we should making two distinct points be Super-Point;
In the case 2, here you need recall the property of P B C C PBCC PBCC;, for any P B C C PBCC PBCC, there has two case:
__1 it contains 1 1 1 Cut-Point (such a P B C C PBCC PBCC is Leaf) (suppose this P B C C PBCC PBCC is { a , S } { a, S } {a,S} where a a a is Cut-Point), then it shows that S S S would be isolated after deleting a a a from G G G, so there must be a Super-Point in S S S (every Leaf-PBCC contains a Super-Point); (if we delete x ≠ a x neq a x=a, all other points in S S S can pass through a a a to another L e a f − P B C C Leaf-PBCC Leaf−PBCC which must contains a Super-Point)
__2 it contains ≥ 2 geq 2 ≥2 Cut-Points; (suppose this P B C C PBCC PBCC is { a , b , S } { a, b, S } {a,b,S} where a , b a,b a,b are Cut-Points), if we delete x x x which a Cut-Point (suppose x = a x=a x=a) then all other points in S S S can pass though b b b to a L e a f − P B C C Leaf-PBCC Leaf−PBCC which must contains Super-Point); also if x x x is not a Cut-Point, the device also valid;