[BZOJ 1061][NOI2008]志愿者招募
膜了一发BYVoid的题解……竟然搞懂了
这首先是个非常简单的线性规划,就是有若干限制(每天要求的志愿者),形如:
\[P_i = X_a + X_b +\ldots + X_c\geq A_i\]
(这里用\(X_i\)表示第\(i\)类志愿者雇佣了多少个,\(P_i\)表示第\(i\)天的志愿者总数,\(A_i\)同原题面)
且最小化总费用。
既然我们我知道\(P_i\geq A_i\),那么说明\(P_i\)一定可以表示为\(A_i + Y_i\)(\(Y_i\geq 0\))。然后这样限制就变成了:
\[P_i = X_a + X_b +\ldots + X_c + Y_i = A_i\]
这个长得很像可以流量平衡的样子,但是流量的变动是表示不了的……
然后假设\(P_0 = 0\)且\(P_{n + 1} = 0\),这样就可以对限制差分一下,我们就有了\(n + 1\)个限制,然后这个式子就可以流量平衡做了(因为不考虑常数项的话,同一变量只可能在两个限制中出现,并且一正一负,这样就可以通过一个限制送给另一个限制流量来表示了。至于常数项,通过源或者汇连边即可表达)。
然后由于志愿者无限,所以这个东西也一定有解……
我局的我这么渣各位看官看懂的可能性基本上是零……还是推荐BYVoid神犇的题解,比我透彻多了。
代码:
/************************************************************** Problem: 1061 User: danihao123 Language: C++ Result: Accepted Time:3164 ms Memory:6824 kb ****************************************************************/ #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <utility> #include <algorithm> #include <queue> #include <cassert> typedef long long ll; int m, n; const int maxno = 100005; const int maxe = 100005; int first[maxno]; int next[maxe], from[maxe], to[maxe]; ll flow[maxe], cap[maxe]; ll cost[maxe]; int gcnt = 0; void add_edge(int u, int v, ll f, ll c) { gcnt ++; next[gcnt] = first[u]; first[u] = gcnt; from[gcnt] = u; to[gcnt] = v; cap[gcnt] = f; flow[gcnt] = 0; cost[gcnt] = c; } int rev(int i) { return ((i - 1) ^ 1) + 1; } int ins_edge(int u, int v, ll f, ll c = 0LL) { #ifdef LOCAL printf("Inserting Edge (%d, %d, %lld, %lld)\n", u, v, f, c); #endif add_edge(u, v, f, c); add_edge(v, u, 0, -c); return gcnt - 1; } const ll LINF = 0x7f7f7f7f7f7f7f7fLL; int tot; bool spfa(int s, int t, ll &f, ll &c) { static ll d[maxno]; static bool inq[maxno]; static ll a[maxno]; static int p[maxno]; std::fill(d, d + tot + 1, LINF); std::fill(inq, inq + tot + 1, false); std::fill(a, a + tot + 1, 0LL); std::fill(p, p + tot + 1, 0); d[s] = 0; std::queue<int> Q; Q.push(s); inq[s] = true; a[s] = LINF; while(!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for(int i = first[u]; i; i = next[i]) { if(cap[i] > flow[i]) { int v = to[i]; if(d[v] > d[u] + cost[i]) { d[v] = d[u] + cost[i]; a[v] = std::min(a[u], cap[i] - flow[i]); p[v] = i; if(!inq[v]) { Q.push(v); inq[v] = true; } } } } } if(a[t] == 0LL) return false; f += a[t]; c += a[t] * d[t]; for(int e = p[t]; e; e = p[from[e]]) { flow[e] += a[t]; flow[rev(e)] -= a[t]; } return true; } void mcmf(int s, int t, ll &f, ll &c) { while(spfa(s, t, f, c)); } const int maxn = 1005, maxm = 10005; int E[maxn]; int A[maxn], D[maxn]; int main() { scanf("%d%d", &n, &m); int s = 0, t = n + 2; tot = n + 2; for(int i = 1; i <= n; i ++) scanf("%d", &A[i]); for(int i = 1; i <= n + 1; i ++) { D[i] = A[i] - A[i - 1]; if(D[i] >= 0) { E[i] = ins_edge(s, i, D[i]); } else { E[i] = ins_edge(i, t, -D[i]); } } for(int i = 1; i <= n; i ++) { ins_edge(i + 1, i, LINF); } while(m --) { int S, T, C; scanf("%d%d%d", &S, &T, &C); ins_edge(S, T + 1, LINF, C); } ll f = 0, c = 0; mcmf(s, t, f, c); printf("%lld\n", c); return 0; }