求乒乓球放入抽屉的算法
有N个乒乓球,要放入N个抽屉,规定每个乒乓球准许放入10个随机指定的抽屉的任意一个,每个抽屉只能放入一个乒乓球。
求一算法,让放不进抽屉的乒乓球最少。
N的数量级在20W。
[解决办法]
显然最大流。n=20w的话点40w,边160w,写个dinic或者sap或者hlpp估计几秒里能出解。
[解决办法]
打错边数了。这个最大流的边数至多能到240w。下面的性能估计没有问题。