Description
给出一个n*m的地图，A[i][j]表示给(i,j)点建立屏障所需费用，现在给出一个点(x,y)，要求用最小代价把(x,y)围住（即上下左右运动最终都会屏障挡住）
Input
第一行四个整数n,m,x,y分别表示地图行列数以及要围住的点坐标，之后一个n*m矩阵A(3<=n,m<=50,2<=x<=n-1,2<=y<=m-1,0<=A[i][j]<=500,A[x][y]=0)
Output
输出最小花费和方案，X表示在该点建立屏障
Sample Input
3 4 2 2
9 1 1 9
1 0 9 1
9 1 1 9
Sample Output
Solution
把(x,y)看作源点，外界看作汇点，把费用看作流量，那么问题变成用最小花费把源汇点分开，即求该图的最小割，为限流还需把拆点in(i,j)和out(i,j)，建边就是以下几种：
out(1,j)->e,out(n,j)->e,out(i,1)->,out(i,m)->e，流量INF：表示四周的点到汇点建无穷的边
1.s->in(x,y)，流量无穷：表示源点
2.in(i,j)->out(i,j)，流量A[i][j] (i!=x&&j!=y)：每个点的费用用拆点后两个点之间边的流量体现
3.in(x,y)->out(x,y)，流量无穷：为整齐所以用了s,in(x,y),out(x,y),其实直接拿out(x,y)当源点就行
4.out(i,j)->in(ii,jj)（(ii,jj)是(i,j)的上下左右的点），流量无穷：表示相邻点之间移动，没有花费（花费都体现在拆点之间的边上）
跑一遍最大流即求出该图的最小割，至于输出方案，对参与网络dfs，搜到的点就标记，如果一个点拆成的两个点都被打上标记说明该条边不在割集里，即该点不需要建立屏障，如果一个被打标记一个没有说明该条边属于割集，该点需要建立屏障，但是注意到费用有0，所以费用为0的点拆成的两点之间的边不会在残余网络中，如果特殊考虑比较麻烦，不如把所有费用为0的点全部建立屏障，这样不会影响总花费而且方案也是对的
Code
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
#define maxn 5555
#define maxm 1111111
#define INF 0x3f3f3f3f
int head[maxn],cur[maxn],d[maxn],st[maxm],s,e,no;//s为源点,e为汇点,n为点数,no为边数
struct point
{
int u,v,flow,next;
point(){};
point(int x,int y,int z,int w):u(x),v(y),next(z),flow(w){};
}p[maxm];
void add(int x,int y,int z)//从x到y建容量为z的边
{
p[no]=point(x,y,head[x],z);//前向弧,标号为偶
head[x]=no++;
p[no]=point(y,x,head[y],0);//后向弧,标号为奇
head[y]=no++;
}
void init()//初始化
{
memset(head,-1,sizeof(head));
no=0;
}
bool bfs()
{
int i,x,y;
queue<int>q;
memset(d,-1,sizeof(d));
d[s]=0;
q.push(s);
while(!q.empty())
{
x=q.front();
q.pop();
for(i=head[x];i!=-1;i=p[i].next)
{
if(p[i].flow&& d[y=p[i].v]<0)
{
d[y]=d[x]+1;
if(y==e)
return true;
q.push(y);
}
}
}
return false;
}
int dinic()//最大流
{
int i,loc,top,x=s,nowflow,maxflow=0;
while(bfs())
{
memcpy(cur,head,sizeof(head));
top=0;
while(true)
{
if(x==e)
{
nowflow=INF;
for(i=0;i<top;i++)
{
if(nowflow>p[st[i]].flow)
{
nowflow=p[st[i]].flow;
loc=i;
}
}
for(i=0;i<top;i++)
{
p[st[i]].flow-=nowflow;
p[st[i]^1].flow+=nowflow;
}
maxflow+=nowflow;
top=loc;
x=p[st[top]].u;
}
for(i=cur[x];i!=-1;i=p[i].next)
if(p[i].flow&&d[p[i].v]==d[x]+1)
break;
cur[x]=i;
if(i!=-1)
{
st[top++]=i;
x=p[i].v;
}
else
{
if(!top)
break;
d[x]=-1;
x=p[st[--top]].u;
}
}
}
return maxflow;
}
int n,m,x,y,a[55][55],vis[maxn];
int in(int i,int j)
{
return (i-1)*m+j;
}
int out(int i,int j)
{
return (i-1)*m+j+n*m;
}
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
void dfs(int u)
{
for(int i=head[u];~i;i=p[i].next)
{
int v=p[i].v;
if(!vis[v]&&p[i].flow)vis[v]=1,dfs(v);
}
}
int main()
{
while(~scanf("%d%d%d%d",&n,&m,&x,&y))
{
init();
s=0,e=2*n*m+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(i!=x||j!=y)
add(in(i,j),out(i,j),a[i][j]);
add(in(x,y),out(x,y),INF);
add(s,in(x,y),INF);
for(int i=1;i<=n;i++)add(out(i,1),e,INF),add(out(i,m),e,INF);
for(int j=2;j<m;j++)add(out(1,j),e,INF),add(out(n,j),e,INF);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=0;k<4;k++)
{
int ii=i+dx[k],jj=j+dy[k];
if(ii<1||ii>n||jj<1||jj>m)continue;
add(out(i,j),in(ii,jj),INF);
}
int ans=dinic();
printf("%d\n",ans);
memset(vis,0,sizeof(vis));
vis[s]=1;
dfs(s);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
if(!(i==x&&j==y)&&((vis[in(i,j)]^(vis[out(i,j)]))||a[i][j]==0))printf("X");
else printf(".");
printf("\n");
}
}
}