Gold Mine

1
2
1
10 100 0
2
10 100 1
1 1
10 100 1
1 1

Case #1: 270

题意：有一些金矿区域，挖一个金矿时必须挖掉上边的跟他关联的，为最多赚的钱数。输入解释：第一个行是样例的组数。第二行表示有n个区域,接下来的一行m表示第i个区域的金矿的个数为m。接下来的m行为这个区域金矿花费的钱数，获得钱数，以及相关连的金矿的个数w，（下面的w行就是表示这些相关联的金矿的区域和在这个区域的第几个）。

思路：最大闭合图。类似poj 2987.建图时把每层的金矿数固定，然后编号建边。

代码：

/* ***********************************************
Author :rabbit
Created Time :2014/3/8 22:19:12
File Name :treap2.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 10000000000000LL
#define eps 1e-8
#define pi acos(-1.0)
typedef __int64 ll;
const ll maxn=3199;
const ll maxm=400010;
struct Edge{
    ll to,next,cap,flow;
    Edge(){};
    Edge(ll _next,ll _to,ll _cap,ll _flow)`{
        next=_next;to=_to;cap=_cap;flow=_flow;
    }
}edge[maxm];
ll head[maxn],tol,gap[maxn],dep[maxn],cur[maxn];
void addedge(ll u,ll v,ll flow){
    edge[tol]=Edge(head[u],v,flow,0);head[u]=tol++;
    edge[tol]=Edge(head[v],u,0,0);head[v]=tol++;
}
ll Q[maxn];
void bfs(ll start,ll end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]++;ll front=0,rear=0;
    dep[end]=0;Q[rear++]=end;
    while(front!=rear){
        ll u=Q[front++];
        for(ll i=head[u];i!=-1;i=edge[i].next){
            ll v=edge[i].to;if(dep[v]==-1&&edge[i].cap)
                Q[rear++]=v,dep[v]=dep[u]+1,gap[dep[v]]++;
        }
    }
}
ll S[maxn];
ll sap(ll start,ll end,ll N){
    bfs(start,end);
    memcpy(cur,head,sizeof(head));
    ll top=0,u=start,ans=0;
    while(dep[start]<N){
        if(u==end){
            ll MIN=INF,id;
            for(ll i=0;i<top;i++)
                if(MIN>edge[S[i]].cap-edge[S[i]].flow)
                    MIN=edge[S[i]].cap-edge[S[i]].flow,id=i;
            for(ll i=0;i<top;i++)
                edge[S[i]].flow+=MIN,edge[S[i]^1].flow-=MIN;
            ans+=MIN,top=id,u=edge[S[top]^1].to;
            continue;
        }
        bool flag=0;ll v;
        for(ll i=cur[u];i!=-1;i=edge[i].next){
            v=edge[i].to;
            if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u]){
                flag=1;cur[u]=i;break;
            }
        }
        if(flag){
            S[top++]=cur[u];u=v;continue;
        }
        ll MIN=N;
        for(ll i=head[u];i!=-1;i=edge[i].next)
            if(edge[i].cap-edge[i].flow&&dep[edge[i].to]<MIN)
                MIN=dep[edge[i].to],cur[u]=i;
        if(--gap[dep[u]]==0)break;gap[dep[u]=MIN+1]++;
        if(u!=start)u=edge[S[--top]^1].to;
    }
    return ans;
}
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     ll T,t;
	 scanf("%I64d",&T);
	 for(ll t=1;t<=T;t++){
		 memset(head,-1,sizeof(head));tol=0;
		 ll sum=0;
		 ll laynum;
		 scanf("%I64d",&laynum);
		 for(ll i=1;i<=laynum;i++){
			 ll jin;
			 scanf("%I64d",&jin);
			 for(ll j=1;j<=jin;j++){
				 ll a,b,c;
				 scanf("%I64d%I64d%I64d",&a,&b,&c);
				 b-=a;
				 if(b>0){
					 sum+=b;
					 addedge(0,i*26+j,b);
				 }
				 else addedge(i*26+j,3000,-b);
				 while(c--){
					 ll u,v;
					 scanf("%I64d%I64d",&u,&v);
					 addedge(i*26+j,u*26+v,INF);
				 }
			 }
		 }
		 ll cnt=sap(0,3000,10000);
		  printf("Case #%I64d: %I64d\n",t,sum-cnt);  
	 }
     return 0;
}

hdu 3996 最大权闭合子图,布布扣,bubuko.com

hdu 3996 最大权闭合子图

原文：http://blog.csdn.net/xianxingwuguan1/article/details/20802505