[CF#290 Div.1 C]Fox And Dinner(最大流)

题目:http://codeforces.com/contest/512/problem/C

题目大意:给你若干个数,让你分成k组,每组围成一个圆,使得相邻两个数和均为素数,且每组人数应>=3个。输出方案

分析:不容易想到最大流。

官方解答:

因为每个数都>=2,所以素数一定是由一个奇数+一个偶数,即一个奇数两边的必须为偶数,一个偶数的周围的必须是奇数。

于是考虑:

若一个奇数和一个偶数的和为素数,那么在它们之间连上双向边,权值为1 

因为每个奇数要连两个偶数,每个偶数要连两个奇数,所以可以弄个点S向所有奇数点连上权值为2的边,所有偶数点向T连上边权为2的边

如果有结果,那么肯定是一个一个的圈,即S连向奇数点的边和偶数点连向T的边都满流。方案直接在残留网络上dfs就行了。

原文地址:https://www.cnblogs.com/wmrv587/p/4290981.html