线性规划费用流解法(Bzoj1061: [Noi2008]志愿者招募)

时间:2023-03-09 19:31:18
线性规划费用流解法(Bzoj1061: [Noi2008]志愿者招募)

题面

传送门

Sol

线性规划费用流解法用与求解未知数为非负数的问题

这道题可以列出一堆形如

\(x[i]+x[j]+x[k]+...>=a[p]\)

的不等式

我们强行给每个式子减去一个东西,使他变成这样

\(x[i]+x[j]+x[k]+...-y[p]==a[p]\)

然后相邻两个式子差分一下

把每个式子看成一个点

那么这样后,在这个题中所有的未知数只会出现在一个方程中

等式左边符号是正的向符号为负的方程连边,费用为代价,如果是补的未知数\(y\),那么费用为零

右边的数是正的连\(s\),否则连\(t\)

费用流出解

# include <bits/stdc++.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll; IL int Input(){
RG int x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
} const int maxn(1005);
const int inf(1e9); int n, m, first[maxn], cnt, ans, s, t;
int dis[maxn], pre1[maxn], pre2[maxn], vis[maxn];
queue <int> q; struct Edge{
int to, next, f, w;
} edge[maxn * 25]; IL void Add(RG int u, RG int v, RG int f, RG int w){
edge[cnt] = (Edge){v, first[u], f, w}, first[u] = cnt++;
edge[cnt] = (Edge){u, first[v], 0, -w}, first[v] = cnt++;
} IL int Aug(){
for(RG int i = s; i <= t; ++i) dis[i] = inf;
q.push(s), dis[s] = 0, vis[s] = 1;
while(!q.empty()){
RG int u = q.front(); q.pop();
for(RG int e = first[u]; e != -1; e = edge[e].next){
RG int v = edge[e].to;
if(edge[e].f && dis[v] > dis[u] + edge[e].w){
dis[v] = dis[u] + edge[e].w;
pre1[v] = e, pre2[v] = u;
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
vis[u] = 0;
}
if(dis[t] == inf) return 0;
RG int ret = inf;
for(RG int p = t; p; p = pre2[p]) ret = min(ret, edge[pre1[p]].f);
ans += ret * dis[t];
for(RG int p = t; p; p = pre2[p])
edge[pre1[p]].f -= ret, edge[pre1[p] ^ 1].f += ret;
return 1;
} int main(){
n = Input(), m = Input();
s = 0, t = n + 2;
for(RG int i = s; i <= t; ++i) first[i] = -1;
RG int last = 0;
for(RG int i = 1; i <= n; ++i){
RG int v = Input();
if(v - last > 0) Add(s, i, v - last, 0);
else if(v - last < 0) Add(i, t, last - v, 0);
last = v, Add(i + 1, i, inf, 0);
}
Add(n + 1, t, last, 0);
for(RG int i = 1; i <= m; ++i){
RG int l = Input(), r = Input(), c = Input();
Add(l, r + 1, inf, c);
}
while(Aug());
printf("%d\n", ans);
return 0;
}