[ZJOI2013] 防守战线
题目描述
战线可以看作一个长度为 $n$ 的序列，现在需要在这个序列上建塔来防守敌兵，在序列第 $i$ 号位置上建一座塔有 $C_i$ 的花费，且一个位置可以建任意多的塔，费用累加计算。有 $m$ 个区间 $[L_1, R_1], [L_2, R_2], \cdots, [L_m, R_m]$ ，在第 $i$ 个区间的范围内要建至少 $D_i$ 座塔。求最少花费。
$n\le 1000$ ， $m\le 10000$ ， $1\le L_i\le R_i\le n$ ，其余数据均 $\le 10000$ 。
题解
设 $p_i$ 表示前 $i$ 个位置建的数量，则有：
$$\min\left\{\sum(p_i-p_{i-1})C_i~|~p_{R_i}-p_{L_i-1}\geq D_i,p_i-p_{i-1}\ge0\right\} $$
即
$$\min\left\{\sum p_i(C_i-C_{i-1})~|~p_{R_i}-p_{L_i-1}\geq D_i,p_i-p_{i-1}\ge0\right\} $$
到这里式子推导有一步很妙的步骤：考虑后面两个条件不等式与前面合并，发现这是在 $\min$ 里面，如果不合法（即 $p_{R_i}-p_{L_i-1}<D_i$ 或 $p_i-p_{i-1}<0$ ），就让它取无穷大，让无穷来限定不合法方案：
$$\min\left\{\sum p_i(C_i-C_{i+1})+\sum\infty\max(D_i-p_{R_i}+p_{L_i-1},0)+\sum\infty\max(p_{i-1}-p_i,0)\right\} $$
然后发现这是费用流模型的对偶，直接费用流做。
代码
90pts
人傻常数大，自己写的费用流 90pts。
const int N = 1e4 + 10, M = 3e4 + 5;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
namespace Main {
const int inf = 707406378;
struct NetworkFlow {
int S, T, n;
int head[N], tot = 1;
struct Edge {
int to; int w, c; int nxt;
} e[M << 1];
void add_edge(int u, int v, int w, int c) {
e[++tot] = (Edge) {v, w, c, head[u]}, head[u] = tot;
e[++tot] = (Edge) {u, 0, -c, head[v]}, head[v] = tot;
}
NetworkFlow() {tot = 1;}
bool vis[N];
int dis[N];
deque <int> q;
bool spfa() {
while (!q.empty()) q.pop_back();
for (int i = 1; i <= n; i++) vis[i] = 0, dis[i] = inf;
dis[T] = 0, vis[T] = 1;
q.push_back(T);
while (!q.empty()) {
int u = q.front(); q.pop_front(); vis[u] = 0;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] > dis[u] - e[i].c && e[i ^ 1].w) {
dis[v] = dis[u] - e[i].c;
if (!vis[v]) {
vis[v] = 1;
if (q.size() && dis[v] < dis[q.front()]) q.push_front(v);
else q.push_back(v);
}
}
}
}
return dis[S] < inf;
}
int mcost = 0;
int dfs (int u, int flow) {
vis[u] = 1;
if (u == T || !flow) return flow;
int sum = 0;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] == dis[u] - e[i].c && e[i].w && !vis[v]) {
int f = dfs(v, min(e[i].w, flow - sum));
if (!f) continue;
e[i].w -= f;
e[i ^ 1].w += f;
sum += f;
mcost += f * e[i].c;
if (sum == flow) break;
}
}
return sum;
}
int mcmf () {
int ret = 0;
while (spfa()) {
vis[T] = 1;
for (; vis[T]; ret += dfs(S, inf))
for (int i = 1; i <= n; i++) vis[i] = 0;
}
return ret;
}
} nf;
int n, m;
int c[N];
int main () {
n = Read(), m = Read();
nf.S = n + 2, nf.n = nf.T = n + 3;
for (int i = 1; i <= n; i++) nf.add_edge(i + 1, i, inf, 0);
for (int i = 1; i <= n; i++) c[i] = Read();
for (int i = 0; i <= n; i++) {
if (c[i] - c[i + 1] > 0) nf.add_edge(nf.S, i + 1, c[i] - c[i + 1], 0);
else nf.add_edge(i + 1, nf.T, c[i + 1] - c[i], 0);
}
for (int i = 1; i <= m; i++) {
int l = Read(), r = Read(); int w = Read();
nf.add_edge(r + 1, l, inf, -w);
}
nf.mcmf();
printf ("%d\n", -nf.mcost);
return 0;
}
}
int main () {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
Main::main();
return 0;
}
100pts
看了提交记录里一位大佬跑得飞快的代码，抄了些优化，AC 了。记记卡常和优化方法。
const int N = 1e3 + 10, M = 3e4 + 5;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
namespace Main {
const int inf = 707406378;
struct NetworkFlow {
int S, T, n;
int head[N], tot = 1;
int cur[N];
struct Edge {
int to; int w, c; int nxt;
} e[M << 1];
void add_edge(int u, int v, int w, int c) {
e[++tot] = (Edge) {v, w, c, head[u]}, head[u] = tot;
e[++tot] = (Edge) {u, 0, -c, head[v]}, head[v] = tot;
}
NetworkFlow() {tot = 1;}
bool vis[N], in[N];
int dis[N], de[N];
int q[M << 4], bk, ft;
void spfa() {
for (int i = 1; i <= n; i++) vis[i] = 0, dis[i] = inf;
dis[S] = 0, vis[S] = 1;
q[ft = bk = 1] = S;
while (ft <= bk) {
int u = q[ft]; ft++; vis[u] = 0;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] > dis[u] + e[i].c && e[i].w) {
dis[v] = dis[u] + e[i].c;
if (!vis[v]) {
vis[v] = 1;
q[++bk] = v;
}
}
}
}
}
int mcost = 0;
int dfs (int u, int flow) {
if (u == T || !flow) {mcost += dis[u] * flow; return flow;}
vis[u] = in[u] = 1;
int sum = 0;
for (int &i = cur[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (!e[i].w) continue;
int d = dis[u] + e[i].c - dis[v];
de[v] = min(de[v], d);
if (d == 0 && !in[v]) {
int f = dfs(v, min(e[i].w, flow - sum));
if (!f) continue;
e[i].w -= f;
e[i ^ 1].w += f;
sum += f;
if (sum == flow) break;
}
}
in[u] = 0;
return sum;
}
int mcmf () {
int ret = 0;
spfa();
while (1) {
for (int i = 1; i <= n; i++) vis[i] = 0, de[i] = inf, cur[i] = head[i];
ret += dfs (S, inf);
int tmp = inf;
for (int i = 1; i <= n; i++) if (!vis[i]) tmp = min(tmp, de[i]);
if (tmp == inf) break;
for (int i = 1; i <= n; i++) if (!vis[i]) dis[i] += tmp;
}
return ret;
}
} nf;
int n, m;
int c[N];
int main () {
n = Read(), m = Read();
nf.S = n + 2, nf.n = nf.T = n + 3;
for (int i = 1; i <= n; i++) nf.add_edge(i + 1, i, inf, 0);
for (int i = 1; i <= n; i++) c[i] = Read();
for (int i = 0; i <= n; i++) {
if (c[i] - c[i + 1] > 0) nf.add_edge(nf.S, i + 1, c[i] - c[i + 1], 0);
else nf.add_edge(i + 1, nf.T, c[i + 1] - c[i], 0);
}
for (int i = 1; i <= m; i++) {
int l = Read(), r = Read(); int w = Read();
nf.add_edge(r + 1, l, inf, -w);
}
nf.mcmf();
printf ("%d\n", -nf.mcost);
return 0;
}
}
int main () {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
Main::main();
return 0;
}
EOF
P3337