网络流专题 Open-Pit Mining （最大权闭合子图）

 Open-Pit Mining

时间限制: 1 Sec  内存限制: 128 MB
提交: 41  解决: 23
[提交] [状态] [讨论版] [命题人:admin]

题目描述

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.

 

输入

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 a single integer giving the maximum profit that ACM can achieve from the given piece of land.

 

样例输入

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

 

样例输出

2

 

来源/分类

RMRC2017 

 

题目大意：给出一些矿井，有一个收益和花费，要开发当前矿井，必须要先开发挡住当前矿井的矿井。

由于开发每一个矿井有一个前提就是开发另外一些矿，如果把当前矿与其他矿连边，就会发现符合闭合子图的定义（如果选当前的点，他的所有出边也要选。）

所以根据求最大权闭合子图的方法，我们将所有权值为正的点与原点连边,所有权值为负的点与汇点连线。

一个结论：权闭合子图的最大权值为所有正权值的边之和减去最小割。

选择的方案就是割集S原点所在的集合。

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#include<cstring>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define sca(x) scanf("%d",&x)
#define per(i,j,k) for(int i=j;i>=k;i--)
#define inf 0x3f3f3f3f
#define LL long long
#define N 1600
#define inf 0x3f3f3f3f
 
int n;
struct edg
{
    int to,w,nt;
}g[N];
 
int dep[205],head[205];
bool bfs(int s,int t)
{
    memset(dep,0,sizeof(dep));
    dep[s]=1;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=g[i].nt)
        {
            int to=g[i].to;
            if(!dep[to]&&g[i].w>0)
            {
                dep[to]=dep[u]+1;
                q.push(to);
            }
        }
    }
    return dep[t]>0;
}
 
int dfs(int s,int flow)
{
    int now=0;
    if(s==n+1)return flow;
    for(int i=head[s];i!=-1;i=g[i].nt)
    {
        int to=g[i].to;
        if(dep[to]==dep[s]+1&&g[i].w>0
           &&(now=dfs(to,min(flow,g[i].w))))
        {
            g[i].w-=now;
            g[i^1].w+=now;
            return now;
        }
    }
    return 0;
}
 
int dinic(int s,int t)
{
    int ans=0;
    int d;
    while(bfs(s,t)){
        while(d=dfs(s,inf))
            ans+=d;
    }
    return ans;
}
 
int tot;
void addedg(int u,int v,int w)
{
    g[tot].to=v;
    g[tot].w=w;
    g[tot].nt=head[u];
    head[u]=tot++;
 
    g[tot].to=u;
    g[tot].w=0;
    g[tot].nt=head[v];
    head[v]=tot++;
}
 
int main()
{
    sca(n);
    int sum=0;
    tot=0;
    memset(head,-1,sizeof(head));
    rep(i,1,n)
    {
        int c,v,k;
        scanf("%d%d%d",&v,&c,&k);
        if(v-c>=0)addedg(0,i,v-c),sum+=v-c;
        else addedg(i,n+1,c-v);
        rep(j,1,k)
        {
            int tmp;
            sca(tmp);
            addedg(tmp,i,inf);
        }
    }
    printf("%d\n",sum-dinic(0,n+1));
}