CSU2114 Open-Pit Mining（最大权闭合子图）

Open-Pit Mining

Description

Open-pit mining is a surface mining technique of extracting rock or minerals from the earth by their removal from an open pit or borrow. Open-pit mines are used when deposits of commercially useful minerals or rocks are found near the surface. Automatic Computer Mining (ACM) is a company that would like to maximize its profits by open-pit mining. ACM has hired you to write a program that will determine the maximum profit it can achieve given the description of a piece of land.

Each piece of land is modelled as a set of blocks of material. Block i has an associated value (vi), as well as a cost (ci), to dig that block from the land. Some blocks obstruct or bury other blocks. So for example if block i is obstructed by blocks j and k, then one must first dig up blocks j and k before block i can be dug up. A block can be dug up when it has no other blocks obstructing it.

Input

The first line of input is an integer N(1≤N≤200) which is the number of blocks. These blocks are numbered 1 through N. Then follow N lines describing these blocks. The ith such line describes block i and starts with two integers vi, ci denoting the value and cost of the ith block (0≤vi,ci≤200) . Then a third integer 0≤mi≤N−1 on this line describes the number of blocks that block i obstructs. Following that are mi distinct space separated integers between 1 and N (but excluding i) denoting the label(s) of the blocks that block i obstructs. You may assume that it is possible to dig up every block for some digging order. The sum of values mi over all blocks i will be at most 500.

Output

Output a single integer giving the maximum profit that ACM can achieve from the given piece of land.

Sample Input

5
0 3 2 2 3
1 3 2 4 5
4 8 1 4
5 3 0
9 2 0

Sample Output

2

链接

http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2114

题意

现有n块土地，每开采一块土地可以获利v但是需要支出成本c，一些土地会影响其他土地的开采，一块土地能被开采的条件是没有任何其他土地能影响它，也就是在开采它之前把能影响它的土地先开采了。

题解

最大权闭合子图裸题。

最大权闭合子图，用最小割解决，建立源点 S，向每块土地建一条流量为该土地价值的边，建立汇点 T，每块土地向汇点建立一条流量为该土地开采成本的边，中间土地与土地的依赖关系，如果 a 影响 b，则建立一条 b 向 a 的流量为正无穷的边，跑一遍最大流，求出来的就是该图的最小割，用∑v[i] - 最小割就是答案。

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 510;
const int maxm = 250010;
int N, NP, NC;
const int inf = 0x3f3f3f3f;
struct Edge
{
    int u, v, cap;
    Edge() {}
    Edge(int u, int v, int cap): u(u), v(v), cap(cap) {}
} es[maxm];
int R, S, T;
vector<int> tab[maxn]; // 边集
int dis[maxn];
int current[maxn];
void addedge(int u, int v, int cap)
{
    tab[u].push_back(R);
    es[R++] = Edge(u, v, cap); // 正向边
    tab[v].push_back(R);
    es[R++] = Edge(v, u, 0); // 反向边容量为0
    // 正向边下标通过异或就得到反向边下标, 2 ^ 1 == 3 ; 3 ^ 1 == 2
}
int BFS()
{
    queue<int> q;
    q.push(S);
    memset(dis, 0x3f, sizeof(dis));
    dis[S] = 0;
    while (!q.empty())
    {
        int h = q.front();
        q.pop();
        for (int i = 0; i < tab[h].size(); i++)
        {
            Edge &e = es[tab[h][i]];
            if (e.cap > 0 && dis[e.v] == 0x3f3f3f3f)
            {
                dis[e.v] = dis[h] + 1;
                q.push(e.v);
            }
        }
    }
    return dis[T] < 0x3f3f3f3f; // 返回是否能够到达汇点
}
int dinic(int x, int maxflow)
{
    if (x == T)
        return maxflow;
    // i = current[x] 当前弧优化
    for (int i = current[x]; i < tab[x].size(); i++)
    {
        current[x] = i;
        Edge &e = es[tab[x][i]];
        if (dis[e.v] == dis[x] + 1 && e.cap > 0)
        {
            int flow = dinic(e.v, min(maxflow, e.cap));
            if (flow)
            {
                e.cap -= flow; // 正向边流量降低
                es[tab[x][i] ^ 1].cap += flow; // 反向边流量增加
                return flow;
            }
        }
    }
    return 0; // 找不到增广路 退出
}

int DINIC()
{
    int ans = 0;
    while (BFS()) // 建立分层图
    {
        int flow;
        memset(current, 0, sizeof(current)); // BFS后应当清空当前弧数组
        while (flow = dinic(S, 0x3f3f3f3f)) // 一次BFS可以进行多次增广
            ans += flow;
    }
    return ans;
}

int main()
{
    int n,u, v, m, x;
    scanf("%d", &n);
    R = 0, S = 0, T = n + 1;
    int sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d%d%d", &u, &v, &m);
        if (u > v)
        {
            addedge(S, i, u - v); // 土地与源点
            sum += (u - v);
        }
        else
            addedge(i, T, v - u); // 土地与汇点
        for (int j = 0; j < m; ++j)
        {
            scanf("%d", &x);
            addedge(x, i, inf);
        }
    }
    printf("%d\n", sum - DINIC());
    return 0;
}

这道题因为板子的问题，wa了好多次，最后才知道是异或得到反向边的问题，还是自己太菜了，对板子理解的不深刻，如果需要详细解释可以参考雪的期许的题解。就讲这么多，面壁思过去了。

The end.
2018-05-27 星期日