首页 > 代码库 > 精辟!

精辟!

观察发现,每个变量都在两个式子中出现了,而且一次为正,一次为负。所有等式右边和为0。接下来,根据上面五个等式构图。

  • 每个等式为图中一个顶点,添加源点S和汇点T。
  • 如果一个等式右边为非负整数c,从源点S向该等式对应的顶点连接一条容量为c,权值为0的有向边;如果一个等式右边为负整数c,从该等式对应的顶点向汇点T连接一条容量为c,权值为0的有向边。
  • 如果一个变量X[i]在第j个等式中出现为X[i],在第k个等式中出现为-X[i],从顶点j向顶点k连接一条容量为∞,权值为V[i]的有向边。
  • 如果一个变量Y[i]在第j个等式中出现为Y[i],在第k个等式中出现为-Y[i],从顶点j向顶点k连接一条容量为∞,权值为0的有向边。

构图以后,求从源点S到汇点T的最小费用最大流,费用值就是结果。

解决noi2008志愿者招募以及Poj3680 Intervals的神器!

步骤

1.列出不等式

2.添加辅助变量,使其变为等式

3.构造p[0]及p[n+1], 差分

4.按上述建图

5.OK