Open-Pit Mining(永远不可能学会的图论之最大权闭合子图）

                                         Open-Pit Mining

                                                                    时间限制: 1 Sec  内存限制: 128 MB
                                                                                  提交: 32  解决: 17
                                                                     [提交] [状态] [讨论版] [命题人: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

【题意】

某公司要开采一些矿井，但是一些矿井会被别的井挡住，必须先开了挡住的井。每个井有个开采价值vi，有个开采成本ci

现在可以开采一些矿井，问最大能获得的利润

【题解】

重点是能将此题有最大权闭合子图联系起来。要开采某矿井，必须开采它前面的矿井，符合闭合图。

每个点可以求出利润wi = vi - ci，作为点权。

若i被j挡住，那么就建立边i->j，然后按照最大权闭合子图建图，最大流模板即过。

 

邻接表

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <cstring>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <stdlib.h>
#include <list>
#include <map>
#include <utility>
#include <time.h>
#include <set>
#include <bitset>
#include <vector>
#define pi acos(-1.0)
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define ms(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define ll long long
const int maxn=1e5+5;
using namespace std;
const int MAX=1e6+5;
const int N=1e6+5;
struct node
{
    ll t,cap,flow,next;    //cap容量，flow流量
} e[N];
int head[N],cur[N],cnt; //cur优化dfs中的head
void init()
{
    int cnt=0;
    ms(head,-1);
}
void add(int u,int v,int cap)   //u->v容量为cap
{

    e[cnt].t=v;
    e[cnt].cap=cap;
    e[cnt].flow=0;
    e[cnt].next=head[u];
    //e[cnt]=node{v,cap,0,head[u]};
    head[u]=cnt++;
    //e[cnt]=node{u,0,0,head[v]};
    e[cnt].t=u;//容量为0的反向边
    e[cnt].cap=0;
    e[cnt].flow=0;
    e[cnt].next=head[v];
    head[v]=cnt++;
}
int d[N];    //bfs深度
bool bfs(int s,int t)   //O(n+m)
{
    memset(d,0,sizeof(d));
    queue<int>q;
    q.push(s);
    d[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u]; ~i; i=e[i].next)
        {
            int v=e[i].t;
            if(d[v]==0&&e[i].cap-e[i].flow>0)
            {
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    return d[t]>0;     //存在增广路
}
ll dfs(int s,int t,ll minedge)
{
    if(s==t)return minedge;
    ll flow=0;    //从当前s点流出的流量
    for(int &i=cur[s]; ~i; i=e[i].next)
    {
        int v=e[i].t;
        if(d[v]==d[s]+1&&e[i].cap-e[i].flow>0)   //层次关系&&有剩余流量
        {
            ll temp=dfs(v,t,min(minedge-flow,e[i].cap-e[i].flow));
            e[i].flow+=temp;    //流量增加
            e[i^1].flow-=temp;    //反向边流量减少
            flow+=temp;    //flow已分配的流量
            if(flow==minedge)return flow;  //已达到祖先的最大流，无法再大，剪枝
        }
    }
    if(flow==0)d[s]=0;   //此点已无流，标记掉
    return flow;
}
ll dinic(int s,int t)   //一定要建立反向边cap=0
{
    ll maxflow=0;
    while(bfs(s,t))   //有增广路
    {
        memcpy(cur,head,sizeof(head));   //重要的优化
        maxflow+=dfs(s,t,INF);
    }
    return maxflow;
}
int pro[220];
int main()
{

    int n,u,v,x,k;
    init();
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {

        scanf("%d%d%d",&u,&v,&k);
        pro[i]=u-v;
        while(k--)
        {
            scanf("%d",&x);
            add(x,i,INF);
        }
    }

    ll sum=0;
    for(int i=1; i<=n; i++)
    {

        if(pro[i]>0)
        {

            add(0,i,pro[i]);
            sum+=pro[i];
        }
        else add(i,n+1,-pro[i]);
    }
    int ans=dinic(0,n+1);
    printf("%d\n",sum-ans);

    return 0;

}