【BZOJ1061】【NOI2008】志愿者招募Vol.2

学了单纯形回来再做一下这个题

显然我们可以将这个问题表示为一个线性规划

最小化\(\sum_{i=1}^{m}c_i x_i\)

满足约束
\(\sum_{i=1}^{m}b_{j,i}x_i\ge a_j(j\in[1,n])\)
\(x_i\ge 0(i\in[1,m])\)

其中\(b_{j,i}=\begin{cases}
1,&第i个志愿者在第j天工作\\
0,&第i个志愿者不在第j天工作
\end{cases}\)

直接跑。。显然不方便,还要初始化,而且还是最小化。。

那我们对偶一下不就什么问题都没有了?

最大化\(\sum_{i=1}^{n}a_i y_i\)

满足约束
\(\sum_{i=1}^{n}b_{i,j}y_i\le c_j(j\in[1,m])\)
\(y_i\ge 0(i\in[1,n])\)

再跑就爽多了

代码比费用流短,构造比费用流简单,跑得比费用流快233(唯一的缺点耗空间)

说点什么

1 评论 在 "【BZOJ1061】【NOI2008】志愿者招募Vol.2"

提醒
排序:   最新 | 最旧 | 得票最多
游客

强者!

wpDiscuz