【网络流】 HDU 3468 Treasure Hunting-白红宇

【网络流】 HDU 3468 Treasure Hunting

阅读量：6817 次

发布时间：2019-06-26

本文共 2938 字，大约阅读时间需要 9 分钟。

题意：

A-Z&&a-z 表示集结点

从A点出发经过最短步数走到下一个集结点（A的下一个集结点为B ，Z的下一个集结点为a）的路上遇到金子（*）则能够捡走（一个点仅仅能捡一次）

求从A点出发走遍全部的的集结点最多能捡多少金子

思路：先对于第 i 个集结点用BFS求出对于每一个点从该集结点所需的步数为D[ I ] [ t ]

对于随意一个金子若两个相邻的集结点的最短步数=其到该金子的步数和则建一条边（能够拿）

然后最大流求

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;#include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    ;#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]; //注意是MAXMint 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
                    
                     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
                     
                      =0&&dy