而是Div2的最後一題,當時打比賽的時候還不會最大流。自己能夠把它寫出來然後1A還是很開心的。
題意:
有n個不小于2的整數,現在要把他們分成若幹個圈。在每個圈中,數字的個數不少于3個,而且相鄰的兩個數之和是質數。
分析:
因為每個數都不小于2,是以相加得到的質數一定是奇數,那麼在某個圈中,一定是奇偶相間的。
也就是 奇數相鄰的兩個數是偶數,偶數相鄰的兩個數是奇數。
是以一個圈中的數字一定是偶數個,所有的輸入中也必須是偶數和奇數的個數相同才可能有解。
這轉化為了二分圖比對,其中X是奇數,Y是偶數,如果X和Y中的兩個數加起來是質數,則連一條容量為1的邊。
因為每個奇數的兩邊是偶數,是以将X中的點與源點連一條容量為2的邊。
同樣地,将Y中的點與彙點連一條容量為2的邊。
求一次最大流,如果滿載也就是流量為n的話,說明有解。
輸出解:可以根據求解最大流的時候,找到的路徑,再建一個圖,然後DFS找環。

代碼君