题意简述
给三个点数均为 n 的无向图 G0,G1,G2,构造一张新无向图 W,点数为 n3,每个点的形式为 (x0,x1,x2)。
对于原来 G0 中的一条边 u,v,连接所有 (u,x1,x2),(v,x1,x2)。G1,G2 中的边同理。
点 (x0,x1,x2) 的点权为 Vx0+x1+x2,其中 V=1018。
求 W 的最大权独立集的权值。n,m0,m1,m2≤105。
主要思路
显然贪心优先选 x0+x1+x2 大的是最优的。不妨设所有的边的方向为从权值小的点连向权值大的。
那么一个点被选仅当它的出边中没有点被选。
不妨将其想象成一个公平游戏,则 sg(x0,x1,x2)=mexe((x0,x1,x2),(y0,y1,y2))sg(y0,y1,y2),为 0 则选。
然后观察到三个维度是独立的,可以分开来做。
注意到这样的 SG 函数的上界是 O(√m) 的。
于是甚至不用写 FWT,暴力枚举就好了。