线性规划与网络流24题 - 2 太空飞行计划

#最小割 #网络流 #网络流24题

Published on 2016-03-21

描述

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合，和进行这些实验需要使用的全部仪器的集合。实验 $E_j$ 需要用到的仪器是 $I$ 的子集 $R_j\in I$ 。配置仪器 $I_k$ 的费用为 $c_k$ 美元。实验 $E_j$ 的赞助商已同意为该实验结果支付 $p_j$ 美元。W 教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

分析

不会捉很正常，我开始也不会捉，了解了最小割的建图模型以后，就会捉了。
本题要求最大化总收益，设配置仪器花 $C$ 元，这些仪器能进行的实验的总收益为 $W$ ，不能进行的实验的总收益为 $W'$ ，所有实验的总收益为 $S$ ，则

\text{Profit} = W - C = (S- W') - C = S - (W' + C)

由于 $S$ 是常数，我们将问题转化到了在合法的情况下，让 $W' + C$ 尽量小。
于是构图如下：

源点 $s$ ，汇点 $t$ 。
对于每个实验，建立点 $X_i$ ，同时从 $s$ 向每个 $X_i$ 连边，流量为 $p_i$ 。
对于每个仪器，建立点 $Y_i$ ，同时每个 $Y_i$ 向 $t$ 连边，流量为 $c_i$ 。
对于每个实验，向其所有关联的仪器连边，流量无限大。

于是此图的最大流，便是此图的最小割，也就是最小的 $W' + C$ 。
让我们分析为什么这样是成立的：
割，就是要删掉一些边，使得 $s$ 与 $t$ 之间不联通，删掉的边集我们叫做割，割的值就是删掉的边的流量之和。
而最小割，就是要求最小的割，我们通过建图，跑最小割，来实现将一些变量最小化。
回到本题，如果一个实验要选，那么它对应的仪器必须要选，这是必须满足的条件。每个实验，我们将是否与源点的边割掉表示是否选这个实验，如果选，就是不割，所以为了使 $s\rightarrow t$ 无路可走，必须将其对应的仪器到 $t$ 的边全部割掉，自然的，如果要选某一个仪器，就是要割其到汇点的所有边。
这就说明，任意一个割（无限大的边禁止割），都是一个合法方案，其值等于 $W' + C$ ，所以，最小割的值，就是最小的 $W' + C$ 。
接着考虑输出方案，对于任意的割而言，设其残余网络中源点能够到的点集合为 $S$ ，对于边 $(u, v)$ ，如果，说明他是一条割边。
根据前面的分析，所有到源点的边未被割掉的实验都要选，意味着它与源点联通。而所有到汇点的边被割掉的仪器都得选，也意味这它与源点联通。
所以，在残余网络中与源点联通的实验或是仪器都得选。

为什么不将仪器放在源点一边呢？因为标准程序放在汇点一边了（考虑一个实验的支出等于收入的情况，且它要的仪器无别的实验需要用，这时他应该不选，尽管答案一样！）

代码

//  Created by Sengxian on 3/21/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//    COGS 网络流24题 - 2
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 100 + 3, maxm = 100 + 3, INF = 0x3f3f3f3f;
struct edge {
    int to, cap, rev;
    edge(int to, int cap, int rev): to(to), cap(cap), rev(rev) {}
};
struct Dinic {
    static const int maxNode = maxn + maxm + 10;
    vector<edge> G[maxNode];
    int level[maxNode], iter[maxNode], s, t;
    void addEdge(int f, int t, int cap) {
        G[f].push_back(edge(t, cap, G[t].size()));
        G[t].push_back(edge(f, 0, G[f].size() - 1));
    }
    bool Bfs() {
        memset(level, -1, sizeof level);
        queue<int> q;
        q.push(s), level[s] = 0;
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            for (int i = 0; i < (int)G[cur].size(); ++i) {
                edge &e = G[cur][i];
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[cur] + 1;
                    q.push(e.to);
                }
            }
        }
        return ~level[t];
    }
    int Dfs(int cur, int flow) {
        if (cur == t || flow == 0) return flow;
        for (int &i = iter[cur]; i < (int)G[cur].size(); ++i) {
            edge &e = G[cur][i];
            if (e.cap > 0 && level[cur] + 1 == level[e.to]) {
                int d = Dfs(e.to, min(flow, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int maxFlow(int s, int t) {
        this -> s = s, this -> t = t;
        int flow = 0, d = 0;
        while (Bfs()) {
            memset(iter, 0, sizeof iter);
            while (d = Dfs(s, INF), d > 0) flow += d;
        }
        return flow;
    }
}Dinic;

int m, n, c[maxm];
int main() {
    freopen("shuttle.in", "r", stdin);
    freopen("shuttle.out", "w", stdout);
    m = ReadInt(), n = ReadInt();
    int s = m + n, t = m + n + 1, a, sum = 0;
    for (int i = 0; i < m; ++i) {
        sum += c[i] = ReadInt();
        Dinic.addEdge(s, i + n, c[i]);
        string s;
        getline(cin, s);
        stringstream ss(s);
        while (ss >> a) Dinic.addEdge(i + n, a - 1, INF);
    }
    for (int i = 0; i < n; ++i) Dinic.addEdge(i, t, ReadInt());
    int ans = sum - Dinic.maxFlow(s, t);
    bool flag = false;
    Dinic.Bfs();
    for (int i = n; i < m + n; ++i) {
        if (Dinic.level[i] > 0) {
            if (flag) putchar(' ');
            else flag = true;
            printf("%d", i - n + 1);
        }
    }
    putchar('\n'); flag = false;
    for (int i = 0; i < n; ++i) {
        if (Dinic.level[i] > 0) {
            if (flag) putchar(' ');
            else flag = true;
            printf("%d", i + 1);
        }
    }
    putchar('\n');
    printf("%d\n", ans);
    return 0;    
}

线性规划与网络流24题 QTREE 7 - Query on a tree VII

Sengxian's Blog

线性规划与网络流24题 - 2 太空飞行计划

描述

分析

代码