Gym - 101982E Cops And Robbers 网络流最小割

1.题意：

输入一个n行m列的地图，地图上有k种陷阱底座，每种陷阱必须放在相应底座上，并且有一定的花费。有一只兔子初始位置在'B'处，为了使这只兔子不能逃出地图，必须放置一些陷阱来阻拦它。问怎么样放置陷阱花费最小并且使得兔子逃不出去。若拦不住，则输出-1。

2.分析：

问题可以简化一下问题：使得图内点与图外点两部分不联通的最小花费。

可以看出这是典型的最小割问题，所以关键在于怎么建图。图上起点也就是源点，图外点标记为汇点。

把每个点拆为入点和出点，陷阱点处的流量为花费，其他点处为0.

每个点所能到达的点，连接上边，边的容量为INF，这样，从源点向汇点跑网络流。

由最大流=最小割性质可以知：最大流 = 最小花费，若flow==INF，则说明必定联通。

3.代码:

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 5000 + 7;
char str[50][50];
int n,m,k,head[maxn],tot,dist[maxn],Cost[30],s,t,cur[maxn];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
struct Edge{
   int from,to,next,flow,cap;
}edge[maxn*10];
void addEdge(int a,int b,int c){
   edge[tot].from = a;edge[tot].to = b;edge[tot].cap = c;edge[tot].flow = 0;edge[tot].next = head[a];head[a] = tot++;
   edge[tot].from = b;edge[tot].to = a;edge[tot].cap = 0;edge[tot].flow = 0;edge[tot].next = head[b];head[b] = tot++;
}
bool BFS(){
   memset(dist,0,sizeof(dist));
   dist[s] = 1;
   queue<int> que;
   que.push(s);
   while(!que.empty()){
      int p = que.front();
      que.pop();
      for(int i = head[p];~i;i = edge[i].next){
          int to = edge[i].to;
          if(!dist[to]&&edge[i].cap > edge[i].flow){
             dist[to] = dist[p] + 1;
             que.push(to);
          }
      }
   }
   if(!dist[t])return false;
   return true;
}
int DFS(int pos,int MinFlow){
    if(pos==t||MinFlow==0)return MinFlow;
    int flow = 0;
    for(int &i = cur[pos];~i;i = edge[i].next){
        int to = edge[i].to;
        if(dist[to]==dist[pos]+1&&edge[i].cap > edge[i].flow){
            int res = DFS(edge[i].to,min(MinFlow,edge[i].cap-edge[i].flow));
            edge[i].flow+=res;
            edge[i^1].flow-=res;
            flow+=res;
            MinFlow-=res;
            if(MinFlow==0)break;
        }
    }
    return flow;
}
int Dinic(int st,int et){
   if(st==et)return 0;
   int MaxFlow = 0;
   while(BFS()){
      for(int i = 0;i<=t;i++)cur[i] = head[i];
      int ans = DFS(st,INF);
      if(ans>=INF)return -1;
      MaxFlow+=ans;
   }
   return MaxFlow;
}
int main()
{
    tot = 0;
    memset(head,-1,sizeof(head));
    scanf("%d%d%d",&m,&n,&k);
    for(int i = 0;i<n;i++)scanf("%s",str[i]);
    for(int i = 0;i<k;i++){
        scanf("%d",&Cost[i]);
    }
    t = 2*n*m + 100;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            int id = i*m + j;
            if(str[i][j]=='B')s = id;
            if(str[i][j]=='.'||str[i][j]=='B')addEdge(id,id+n*m,INF);
            else addEdge(id,id+n*m,Cost[str[i][j]-'a']);
            for(int p = 0;p<4;p++){
                int fx = i + dx[p];
                int fy = j + dy[p];
                if(fx>=0&&fx<n&&fy>=0&&fy<m)addEdge(id+n*m,fx*m + fy,INF);
                else addEdge(id+n*m,t,INF);
            }
        }
    }
    printf("%d\n",Dinic(s,t));
    return 0;
}