天天看點

CodeForces Round #290 Fox And Dinner

而是Div2的最後一題,當時打比賽的時候還不會最大流。自己能夠把它寫出來然後1A還是很開心的。

題意:

有n個不小于2的整數,現在要把他們分成若幹個圈。在每個圈中,數字的個數不少于3個,而且相鄰的兩個數之和是質數。

分析:

因為每個數都不小于2,是以相加得到的質數一定是奇數,那麼在某個圈中,一定是奇偶相間的。

也就是 奇數相鄰的兩個數是偶數,偶數相鄰的兩個數是奇數。

是以一個圈中的數字一定是偶數個,所有的輸入中也必須是偶數和奇數的個數相同才可能有解。

這轉化為了二分圖比對,其中X是奇數,Y是偶數,如果X和Y中的兩個數加起來是質數,則連一條容量為1的邊。

因為每個奇數的兩邊是偶數,是以将X中的點與源點連一條容量為2的邊。

同樣地,将Y中的點與彙點連一條容量為2的邊。

求一次最大流,如果滿載也就是流量為n的話,說明有解。

輸出解:可以根據求解最大流的時候,找到的路徑,再建一個圖,然後DFS找環。

CodeForces Round #290 Fox And Dinner
CodeForces Round #290 Fox And Dinner

代碼君

繼續閱讀