Codeforces 724E - Goods transportation

#动态规划 #技巧 #最小割 #网络流 #最大流
Published on 2016-10-09

题目地址

描述

有 n(n≤10000)n(n\le 10000) 座城市，每座城市有 pi(pi≤109)p_i(p_i\le {10}^9) 个单位的物品，能够售出 si(si≤109)s_i(s_i\le {10}^9) 个单位的物品，同时，对于任意 1≤i<j≤n1\le i< j\le n，你都可以从 ii 向 jj 运送 c(c≤109)c(c\le {10}^9) 单位的物品（不可以从 jj 往 ii 运），请问最多能够卖出多少个单位的物品？

分析

此题可用最大流来建模，建立附加源汇 S,TS, T，对于每个城市 ii，连边 (S,i,pi)(S, i, p_i)，连边 (i,T,si)(i, T, s_i)。对于每个 1≤i<j≤n1\le i< j\le n，连边 (i,j,c)(i, j, c)，求出 S→TS\rightarrow T 的最大流就是答案。不过 O(n2)O(n^2) 级别的边数显然会 TLE。
注意到最大流等于最小割，所以我们求出最小割，也就是求出了最大流。本题的构图比较规则，所以导致了割只可能是 ，可用 DP 来求解。

设 f[i][j]f[i][j] 为考虑点 ，从中选 jj 个点放在 VV 中的最小代价，那么有 f[0][0]=0f[0][0] = 0，f[0][i]=∞,i>0f[0][i] = \infty, i > 0，方程也很好得出：

f[i][j]=min(f[i−1][j]+c⋅k+pi,f[i−1][j−1]+si)f[i][j] = \min(f[i - 1][j] + c \cdot k + p_i, f[i - 1][j - 1] + s_i)

答案是 min0≤i≤nf[n][i]\min_{0\le i\le n}f[n][i]。采用滚动数组，就能在 O(n2)O(n^2) 的时间，O(n)O(n) 的空间内完成计算。

技巧：最大流等于最小割，在比较特殊的构图中，最小割可用 DP 求出，此时无需做网络流算法即可求出最大流。

代码

//  Created by Sengxian on 2016/10/09.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Codeforces 724E 网络流 + 最小割 DP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 10000 + 3;
int n, c, p[MAX_N], s[MAX_N];
ll dp[MAX_N];

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), c = ReadInt();
    for (int i = 1; i <= n; ++i) p[i] = ReadInt();
    for (int i = 1; i <= n; ++i) s[i] = ReadInt();
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j > 0; --j)
            dp[j] = min(dp[j] + (ll)c * j + p[i], dp[j - 1] + s[i]);
        dp[0] += p[i];
    }
    printf("%lld\n", *min_element(dp, dp + n + 1));
    return 0;
}
Codeforces 724C - Ray Tracing