首页 > 代码库 > 【网络流】 HDU 3468 Treasure Hunting
【网络流】 HDU 3468 Treasure Hunting
题意:
A-Z&&a-z 表示 集结点
从A点出发经过 最短步数 走到下一个集结点(A的下一个集结点为B ,Z的下一个集结点为a) 的路上遇到金子(*)则能够捡走(一个点仅仅能捡一次)
求从A点出发走遍全部的的集结点 最多能捡多少金子
思路:先对于第 i 个集结点用BFS求出 对于每一个点从该集结点所需的步数 为D[ I ] [ t ]
对于随意一个金子若 两个相邻的集结点的最短步数=其到该金子的步数和 则建一条边(能够拿)
然后最大流求
#include <cstdio> #include <cstring> #include <cstdlib> #include <string> #include <iostream> #include <algorithm> #include <sstream> #include <cmath> using namespace std; #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> #include <time.h>; #define cler(arr, val) memset(arr, val, sizeof(arr)) #define FOR(i,a,b) for(int i=a;i<=b;i++) #define IN freopen ("in.txt" , "r" , stdin); #define OUT freopen ("out.txt" , "w" , stdout); typedef long long LL; const int MAXN = 10014; const int MAXM = 41001; const int INF = 0x3f3f3f3f; const int mod = 1000000007; struct Edge { int to,next,cap,flow; } edge[MAXM]; //注意是MAXM int tol; int head[MAXN]; int gap[MAXN],dep[MAXN],cur[MAXN]; void init() { tol = 0; memset(head,-1,sizeof (head)); } void addedge (int u,int v,int w,int rw = 0) { edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0; edge[tol].next = head[u]; head[u] = tol++; edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0; edge[tol].next = head[v]; head[v] = tol++; } int Q[MAXN]; void BFS(int start,int end) { memset(dep,-1,sizeof(dep)); memset(gap,0,sizeof(gap)); gap[0] = 1; int front = 0, rear = 0; dep[end] = 0; Q[rear++] = end; while(front != rear) { int u = Q[front++]; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i]. to; if(dep[v] != -1)continue; Q[rear++] = v; dep[v] = dep[u] + 1; gap[dep[v]]++; } } } int S[MAXN]; int sap(int start,int end, int N) { BFS(start,end); memcpy(cur,head,sizeof(head)); int top = 0; int u = start; int ans = 0; int i; while(dep[start] < N) { if(u == end) { int Min = INF; int inser; for( i = 0; i < top; i++) { if(Min > edge[S[i]].cap - edge[S[i]].flow) { Min = edge[S[i]].cap - edge[S[i]].flow; inser = i; } } for( i = 0; i < top; i++) { edge[S[i]]. flow += Min; edge[S[i]^1].flow -= Min; } ans += Min; top = inser; u = edge[S[top]^1].to; continue; } bool flag = false; int v; for( 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 = true; cur[u] = i; break; } } if(flag) { S[top++] = cur[u]; u = v; continue; } int Min = N; for( 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; } } gap[dep[u]]--; if(!gap[dep[u]]) return ans; dep[u] = Min + 1; gap[dep[u]]++; if(u != start)u = edge[S[--top]^1].to; } return ans; } char s[103][103]; bool vis[103][103]; int goal[103*103]; int ral[103*103]; int d[53][101*101]; int n,m; int xx[4]= {1,0,-1,0}; int yy[4]= {0,-1,0,1}; void bfs(int x) { memset(d[x],INF,sizeof(d[x])); cler(vis,false); queue<int>q; int t=ral[x]; vis[t/m][t%m]=true; d[x][t]=0; q.push(t); while(!q.empty()) { t=q.front(); q.pop(); int nx=t/m,ny=t%m; for(int i=0; i<4; i++) { int dx=nx+xx[i],dy=ny+yy[i]; if(dx>=0&&dx<n&&dy>=0&&dy<m&&!vis[dx][dy]&&s[dx][dy]!=‘#‘) { vis[dx][dy]=true; d[x][dx*m+dy]=d[x][t]+1; q.push(dx*m+dy); } } } } int find(char c) { if(‘A‘<=c&&c<=‘Z‘) return c-‘A‘; if(‘a‘<=c&&c<=‘z‘) return c-‘a‘+26; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif while(~scanf("%d%d",&n,&m)) { init(); cler(ral,0); int tol1=0,tol2=0; for(int i=0; i<n; i++) { scanf("%s",s[i]); for(int j=0; j<m; j++) { if(isalpha(s[i][j])) { ral[find(s[i][j])]=i*m+j; tol1++; } else if(s[i][j]==‘*‘) goal[tol2++]=i*m+j; } } for(int i=0; i<tol1; i++) bfs(i); int flag=0; for(int i=1; i<tol1; i++) for(int j=0; j<tol2; j++) { if(d[i][goal[j]]+d[i-1][goal[j]]==d[i-1][ral[i]]) addedge(i,tol1+j,1); if(d[i-1][ral[i]]==INF) flag=1; } if(flag) printf("-1\n"); else { for(int i=1;i<tol1;i++) addedge(0,i,1); for(int i=0;i<tol2;i++) addedge(tol1+i,tol1+tol2,1); printf("%d\n",sap(0,tol1+tol2,tol1+tol2+1)); } } return 0; }
【网络流】 HDU 3468 Treasure Hunting
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。