程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3996 最大權閉合子圖

hdu 3996 最大權閉合子圖

編輯：C++入門知識

Gold Mine

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1882 Accepted Submission(s): 415

Problem Description Long long ago, there is a gold mine.The mine consist of many layout, so some area is easy to dig, but some is very hard to dig.To dig one gold, we should cost some value and then gain some value. There are many area that have gold, because of the layout, if one people want to dig one gold in some layout, he must dig some gold on some layout that above this gold's layout. A gold seeker come here to dig gold.The question is how much value the gold he can dig, suppose he have infinite money in the begin.
Input First line the case number.(<=10)

Then for every case:
one line for layout number.(<=100)
for every layout
first line gold number(<=25)
then one line for the dig cost and the gold value(32bit integer), the related gold number that must be digged first(<=50)

then w lines descripte the related gold followed, each line two number, one layout num, one for the order in that layout
see sample for details
Output Case #x: y.
x for case number, count from 1.
y for the answer.
Sample Input

Sample Output

Case #1: 270

Source 2011 Multi-University Training Contest 16 - Host by TJU
Recommend lcy | We have carefully selected several similar problems for you: 4000 3999 3993 1274 2059

題意：有一些金礦區域，挖一個金礦時必須挖掉上邊的跟他關聯的，為最多賺的錢數。輸入解釋：第一個行是樣例的組數。第二行表示有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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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]edge[S[i]].cap-edge[S[i]].flow)
                    MIN=edge[S[i]].cap-edge[S[i]].flow,id=i;
            for(ll i=0;i0){
					 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;
}