题意：给你一个长为m，宽为n的迷宫，问你从s开始，我们需要最小的花费堵住s，使得s不能到达迷宫的边界，只有字符a,b,c,d,...这样的点才能花费对应的钱将其堵住

解题思路：思考一下，裸的最小割，就是点权需要拆点，每个点拆成对应的两个点，能堵住的点拆为两个点，连条边边权为对应的花费，不能堵的点，连边，边权为inf；

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define maxn 10005#define inf 0x3f3f3f3fusing namespace std;struct Edge{    int next;    int to;    int w;}edge[maxn];int cnt;int head[maxn];int cur[maxn];int depth[maxn];int Start,End,n,m,c;void add(int u,int v,int w){    edge[cnt].next=head[u];edge[cnt].w=w;    edge[cnt].to=v;head[u]=cnt++;    edge[cnt].next=head[v];edge[cnt].w=0;    edge[cnt].to=u;head[v]=cnt++;}bool bfs(){    memset(depth,0,sizeof(depth));    depth[Start]=1;    queue
          
           que;que.push(Start); while(!que.empty()) { int u=que.front();que.pop(); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(!depth[v]&&edge[i].w>0) { depth[v]=depth[u]+1;que.push(v); } } } return depth[End];}int dfs(int u,int maxflow){ int tempflow; if(u==End) return maxflow; int add=0; for(int &i=cur[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(depth[v]==depth[u]+1&&edge[i].w>0&&(tempflow=dfs(v,min(maxflow-add,edge[i].w)))) { edge[i].w-=tempflow; edge[i^1].w+=tempflow; add+=tempflow; if(maxflow==add) break; } } return add;}int dinic(){ int ans=0; while(bfs()) { for(int i=0;i<=2*(n*m)+1000;i++) cur[i]=head[i]; while(int temp=dfs(Start,inf)) ans+=temp; } return ans;}int dx[]={ 1,-1,0,0};int dy[]={ 0,0,1,-1};int main(){ char gra[50][50]; memset(head,-1,sizeof(head));cnt=0; int a[30];int flag=0; scanf("%d%d%d",&m,&n,&c); Start=2*(n*m)+100;End=Start+1; for(int i=0;i
           
            =n||tx<0||ty>=m||ty<0) add(tmp+n*m,End,inf); else add(tmp+n*m,(tx*m+ty),inf); } if(gra[i][j]=='B') add(Start,tmp,inf); } } int ans=dinic(); if(ans>=inf) cout<<"-1\n"; else cout<
            
             <