首页 > 代码库 > 【bzoj1061】[NOI2008]志愿者招募 线性规划与费用流
【bzoj1061】[NOI2008]志愿者招募 线性规划与费用流
题目描述
输入
输出
样例输入
3 3
2 3 4
1 2 2
2 3 5
3 3 2
样例输出
14
题解
线性规划与费用流
“事实上任何最大流，最小费用流，上下界网络流都是在解决一个线性规划问题”（摘自 wyfcyx 大爷的ppt）
具体地，在一个网络流问题中，把边看作变量，把点看作限制条件，就会得到一个线性规划问题。
当然，由于网络流的特性，这类线性规划问题只能是：每个变量出现次数为且仅为2次，且1次系数为+1，1次系数为-1。
如果我们能够将这类特殊的线性规划问题转化为网络流问题，就可以圆满地解决原问题。
考虑本题，限制条件就是每天大的志愿者数大于等于规定数量，求 ∑费用*数量 的最小值。
这样可能不是很清楚，这里用样例举例子：
设$x_i$表示第i类志愿者的人数
限制条件：$\begin{cases}x_i\ge0\\x_1\ge2\\x_1+x_2\ge3\\x_2+x_3\ge4\end{cases}$，要最小化$2x_1+5x_2+2x_3$。
我们把不等关系转化为相等关系，可以得到新的限制条件：\begin{cases}x_i\ge0\\y_i\ge0\\x_1=2+y_1\\x_1+x_2=3+y_2\\x_2+x_3=4+y_3\end{cases}。
这样尽管多了几个变量，却把不等关系转化为容易处理的相等关系，易于建图。
但是这样依然不满足我们使用网络流解决线性规划问题的条件，因为变量出现次数不全为2，且系数不为+1和-1。
此时我们想到差分，把0=0分别放到限制条件中相等关系的最上端与最下端，然后上下进行差分并移项，可以得到：$\begin{cases}x_i\ge0\\y_i\ge0\\x_1-y_1-2=0\\x_2+y_1-y_2-1=0\\x_3-x_1+y_2-y_3-1=0\\-x_2-x_3+y_3+4=0\end{cases}$
这样就把限制条件“神奇”地转化为能够使用网络流解决的问题。为什么？因为用到了题目中的“志愿者工作时间是si天到ti天”，即一定是连续的。我们差分的本质是：$x_i$系数为+1时表示第i类志愿者刚开始工作，$x_i$系数为-1时表示第i类志愿者刚结束工作。所以一定是两个时间点。
我们再回过头来看这个线性规划问题。如何来使用网络流来解决它？这用到了网络流“流量守恒”的性质，即除S和T外，流入流量=流出流量。
我们把系数为+1看作要流出的流量，系数为-1看作要流入的流量，那么显然正负相等，符合条件。对于同一个变量的值是固定的，所以应从+1流向-1；对于常数项，系数为+1则从该点流向T，系数为-1则从S流向该点。
由于限制条件是与变量$x_i$有关的，所以在变量$x_i$对应的边上加上费用，然后跑费用流即可出解。
总结一下建图方法：把题目中的n天转化为n个等式，差分得到n+1个，代表图中的点；对于第i类志愿者，加边si->ti+1，容量为inf，费用为ci；加边j-1->j，容量为inf，费用为0，代表限制条件中的y。对于每天需要的志愿者数量$a_i(1\le i\le n+1)$，如果$a_i>a_{i-1}$，则加边S->i，容量为$a_i-a_{i-1}$，费用为0（因为差分后右面系数为正，移项后为负，代表流入）；否咋加边i->T，容量为$a_{i-1}-a_i$，费用为0.
然后跑最小费用最大流出解。
说了这么多其实代码还是很简单的。
#include <cstdio>#include <cstring>#include <queue>#define N 5000#define M 100000#define inf 0x3f3f3f3fusing namespace std;queue<int> q;int a[N] , head[N] , to[M] , val[M] , cost[M] , next[M] , cnt = 1 , s , t , dis[N] , from[N] , pre[N];void add(int x , int y , int v , int c){ to[++cnt] = y , val[cnt] = v , cost[cnt] = c , next[cnt] = head[x] , head[x] = cnt; to[++cnt] = x , val[cnt] = 0 , cost[cnt] = -c , next[cnt] = head[y] , head[y] = cnt;}bool spfa(){ int x , i; memset(from , -1 , sizeof(from)); memset(dis , 0x3f , sizeof(dis)); dis[s] = 0 , q.push(s); while(!q.empty()) { x = q.front() , q.pop(); for(i = head[x] ; i ; i = next[i]) if(val[i] && dis[to[i]] > dis[x] + cost[i]) dis[to[i]] = dis[x] + cost[i] , from[to[i]] = x , pre[to[i]] = i , q.push(to[i]); } return ~from[t];}int mincost(){ int ans = 0 , i , k; while(spfa()) { k = inf; for(i = t ; i != s ; i = from[i]) k = min(k , val[pre[i]]); ans += k * dis[t]; for(i = t ; i != s ; i = from[i]) val[pre[i]] -= k , val[pre[i] ^ 1] += k; } return ans;}int main(){ int n , m , i , x , y , z; scanf("%d%d" , &n , &m) , s = 0 , t = n + 2; for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]) , add(i + 1 , i , inf , 0); for(i = 1 ; i <= m ; i ++ ) scanf("%d%d%d" , &x , &y , &z) , add(x , y + 1 , inf , z); for(i = 1 ; i <= n + 1 ; i ++ ) { if(a[i] - a[i - 1] > 0) add(s , i , a[i] - a[i - 1] , 0); if(a[i] - a[i - 1] < 0) add(i , t , a[i - 1] - a[i] , 0); } printf("%d\n" , mincost()); return 0;}
【bzoj1061】[NOI2008]志愿者招募 线性规划与费用流