NOIP 2010 普及组复赛最后一题 Flow - 最小费用流问题详解

NOIP 2010 普及组复赛最后一题 Flow - 最小费用流问题详解

题目描述

给定一个 n 个点 m 条边的网络流图，每条边有一个下界 l_i 和一个上界 r_i，以及一个费用 c_i。要求你求出从源点到汇点的最小费用流，使得每条边的流量都满足其下界和上界限制。

输入格式

第一行两个整数 n, m，表示点数和边数。

接下来 m 行，每行 3 个整数 a_i, b_i, l_i, r_i, c_i，表示一条从 a_i 到 b_i，下界为 l_i，上界为 r_i，费用为 c_i 的边。

输出格式

输出一个整数，表示所求的最小费用流。如果不存在满足限制条件的流，输出 -1。

数据范围

1 ≤ n, m ≤ 1000, 0 ≤ l_i ≤ r_i ≤ 10³, 0 ≤ c_i ≤ 10³

样例

输入样例：

3 3 1 2 1 2 1 2 3 1 3 2 1 3 0 2 2

输出样例：

3

算法1

最小费用最大流

算法2

(暴力枚举) O(n⁴)

枚举边的流量，检查是否满足下界和上界条件，再计算费用即可。

时间复杂度

O(n⁴)

参考文献

C++ 代码

// 暴力枚举算法
#include <iostream>
using namespace std;

int n, m, l[1005], r[1005], c[1005], flow[1005], ans = 1e9;
int a[1005], b[1005];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i] >> l[i] >> r[i] >> c[i];
    }
    for (int i = 0; i <= (1 << m) - 1; i++) {
        int cost = 0;
        for (int j = 1; j <= m; j++) {
            if ((i >> (j - 1)) & 1) {
                flow[j] = r[j];
                cost += c[j] * flow[j];
            } else {
                flow[j] = l[j];
                cost += c[j] * flow[j];
            }
        }
        // 检查是否满足下界和上界条件
        bool flag = true;
        for (int j = 1; j <= m; j++) {
            if (flow[j] < l[j] || flow[j] > r[j]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            ans = min(ans, cost);
        }
    }
    if (ans == 1e9) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}

算法3

(暴力枚举)

blablabla

时间复杂度

参考文献

C++ 代码