传送门:【HDU】1822 Building roads
题目分析:二分 + 2-sat
首先给出的hate关系以及like关系我们先建边。
设x<<1为x选择连接s1,x<<1|1为x选择连接s2。
u hate v : < u , ~v > , < v , ~u > , < ~u , v > , < ~v , u >
u like v : < u , v > , < ~v , ~u > , < v , u > , < ~u , ~v >
接下来二分任意两个农场间的最大距离。
如果两个农场之间的距离超过设定的最大距离,视为冲突,则建边。
设农场x到s1的距离为x_s1,到s2的距离为x_s2,y同理。
设s1到s2的距离为d......
阅读全文