首页 > ACM题库 > HDU-杭电 > HDU 3996-Gold Mine-图-[解题报告]HOJ
2015
04-14

HDU 3996-Gold Mine-图-[解题报告]HOJ

Gold Mine

问题描述 :

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.

输入:

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

输出:

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

样例输入:

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行就是表示这些相关联的金矿的区域和在这个区域的第几个)。

建图:把点权为b(b>0)的连到源点,边权为b

点权为a(a<0)的连到汇点,边权为a

然后建出原图,原图中所有边权为inf

最后答案为 : 正点权和 – 最大流

#include <iostream>   
#include <string>   
#include <cstring>   
#include <algorithm>   
#include <cstdio>   
#include <cctype>   
#include <queue>   
#include <stdlib.h>   
#include <cstdlib>   
#include <math.h>   
#include <set>   
#include <vector>   
#define inf 10000000000000000 
#define eps 1e-8   
#define N 2502
#define M 10500
#define ll __int64   
using namespace std;  

//M为边数 N为点数 点标从1-n   
struct Edge{  
    ll from, to, cap, nex;  
}edge[M*10];//注意这个一定要够大 不然会re 还有反向弧  
  
ll head[N], edgenum;  
void addedge(ll u, ll v, ll cap){  
    Edge E = { u, v, cap, head[u]};  
    edge[ edgenum ] = E;  
    head[u] = edgenum ++;  
  
    Edge E2= { v, u, 0,   head[v]};  
    edge[ edgenum ] = E2;  
    head[v] = edgenum ++;  
}  
ll sign[N], s, t;  
bool BFS(ll from, ll to){  
    memset(sign, -1, sizeof(sign));  
    sign[from] = 0;  
  
    queue<ll>q;  
    q.push(from);  
    while( !q.empty() ){  
        int u = q.front(); q.pop();  
        for(ll i = head[u]; i!=-1; i = edge[i].nex)  
        {  
            ll v = edge[i].to;  
            if(sign[v]==-1 && edge[i].cap)  
            {  
                sign[v] = sign[u] + 1, q.push(v);  
                if(sign[to] != -1)return true;  
            }  
        }  
    }  
    return false;  
}  
ll Stack[M*4], top, cur[M*4];  
ll dinic(){  
  
    ll ans = 0;  
    while( BFS(s, t) )  
    {  
        memcpy(cur, head, sizeof(head));  
        ll u = s;      top = 0;  
        while(1)  
        {  
            if(u == t)  
            {  
                ll flow = inf, loc;//loc 表示 Stack 中 cap 最小的边  
                for(ll i = 0; i < top; i++)  
                    if(flow > edge[ Stack[i] ].cap)  
                    {  
                        flow = edge[Stack[i]].cap;  
                        loc = i;  
                    }  
  
                    for(ll i = 0; i < top; i++)  
                    {  
                        edge[ Stack[i] ].cap -= flow;  
                        edge[Stack[i]^1].cap += flow;  
                    }  
                    ans += flow;  
                    top = loc;  
                    u = edge[Stack[top]].from;  
            }  
            for(ll i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增广的边的下标  
                if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break;  
            if(cur[u] != -1)  
            {  
                Stack[top++] = cur[u];  
                u = edge[ cur[u] ].to;  
            }  
            else  
            {  
                if( top == 0 )break;  
                sign[u] = -1;  
                u = edge[ Stack[--top] ].from;  
            }  
        }  
    }  
    return ans;  
}  

vector<ll>G[N];
ll n, cnt;
void init(){
	memset(head, -1, sizeof(head)); edgenum = 0;
	cnt = 1;
	for(ll i = 0; i <= n; i++)G[i].clear();
}
ll from, to;
int main(){
	ll T, Cas = 1, i, j, k, m, a, b, u, v;scanf("%I64d",&T);
	from = 0; to = 2501;
	s = 0, t = to;
	while(T--){
			scanf("%I64d",&n);
			init();
			ll sum = 0;
			for(i = 1; i <= n; i++){
				scanf("%I64d",&m);
				G[i].push_back(100000);
				for(j = 1; j <= m; j++)
				{
					scanf("%I64d %I64d %I64d",&a,&b,&k);
					G[i].push_back(cnt++);
					sum += b;
					addedge(from, G[i][j], b);
					addedge(G[i][j], to, a);
					while(k--){
						scanf("%I64d %I64d",&u,&v);
						addedge(G[i][j], G[u][v], inf);
					}
				}
			}
			printf("Case #%I64d: %I64d\n", Cas++, sum - dinic());		
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acmmmm/article/details/21547417


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。