水晶

还是想了一会的。
类似二分图染色,定义三染色。
一个图的三染色的定义:当前点被染成((x+y+z)mod 3)编号颜色。
观察限制。
一个转化:求出一个水晶集合S,使得这个集合中,能量源旁不同时包含权值1/2的点,且S的收益最大。
容易发现这样子求出的答案和原问题的答案相等。
考虑最小割。
考虑一个水晶作为一条边。对于每个水晶,ans+=价值。
s->所有标号为1的水晶/标号为2的水晶向t连接价值的边。
对于所有标号为0的水晶新建两个点,这两个点连接价值的边。
如果某标号为1/2的水晶和某标号为0的水晶冲突,则这两个水晶连inf边。
ans-最大流就是答案。
水晶额外价值可以把所有水晶的价值*=10以避免小数运算

原文地址:https://www.cnblogs.com/ctmlpfs/p/14401640.html