CF550D Regular Bridge

給出一個\(k\)，構造一個無向圖，使得每個點的度數為\(k\)，且存在一個橋。

\(k\le 100\)

題解

​

以下隻是搬運

首先考慮把橋扔掉，原圖變為兩個聯通塊，其中每個聯通塊中有一個點度數為k-1,其他的點度數為k。下面考慮構造其中一個聯通塊。

不妨令該聯通塊點數為n。 注意到當k為偶數時，這一個聯通塊中的總度數應該是nk-1，是一個奇數，而由于是無向圖，每條邊對總度數的貢獻是2，總度數應該是偶數，産生沖突。進而k為偶數時是無解的。

k為奇數時，令n=2k-1，并且将所有點列成三排：第一排和第二排分别有k-1個點，第三排有一個。第三排與第二排之間兩兩連邊，第二排與第一排之間兩兩連邊，再令第一排中第2t-1與第2t個連邊（1<=t<=(k-1)/2）。不難發現這樣一來第二排與第一排每個點的度數是k，第三排一個點度數為k-1，符合我們的需求。另一個聯通塊類似即可，不要忘記将兩個聯通塊中度數為k-1的點相連作為橋。

複雜度是O(k^2)。

代碼看​​這裡​​