题目大意：有一块地，分成nxm块。有的块上长着草，有的块上是荒地。将任何一块长着草的块上的草拔掉都需要花费d个力气，往任何一块荒地上种上草都需要花费f个力气，在草和荒地之间架一个篱笆需要花费b个力气，如果一块草地四周都是荒地，则得花掉4b个力气。现在，要求最外一圈都种上草，草地与荒地之间要用篱笆隔开，最少需要花费多少个力气？
题目分析：有篱笆要把草地和荒地隔开意味着把所有的块分成两个“阵营”。增加源点和汇点，用源点s代表草地“阵营”头领，汇点t代表荒地“阵营”头领，在初始时，从s向所有的草地（在边界处的除外）连一条弧，容量为d，表示该块草地要背叛头领s投奔敌人的代价；从所有的荒地向汇点连一条弧，容量为f，表示该块荒地放弃头领t的代价；对于任意一个块u，向所有与它相邻的v连一条弧，容量为b，表示u与v对立的代价。我们要做的就是用最少的代价这些块分成两个“阵营”，实际上就是求最小割。
CP：第一次用ISAP来写网络流。。。
代码如下：
# include<iostream>
# include<cstdio>
# include<vector>
# include<queue>
# include<cstring>
# include<iostream>
using namespace std;
const int INF=1<<30;
const int maxn=2505;
int n,m;
char p[60][60];
struct Edge
{
int fr,to,cap,fw;
Edge(int fr,int to,int cap,int fw){
this->fr=fr;
this->to=to;
this->cap=cap;
this->fw=fw;
}
};
struct ISAP
{
vector<Edge>edges;
vector<int>G[maxn];
int d[maxn],gap[maxn],p[maxn];
int n,s,t,vis[maxn],cur[maxn];
void init(int n)
{
this->n=n;
edges.clear();
for(int i=0;i<n;++i) G[i].clear();
}
void addEdge(int u,int v,int cap)
{
edges.push_back(Edge(u,v,cap,0));
edges.push_back(Edge(v,u,0,0));
int m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
void bfs(int u)
{
memset(vis,0,sizeof(vis));
d[u]=0;
queue<int>q;
q.push(u);
vis[u]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<G[x].size();++i){
Edge &e=edges[G[x][i]];
if(e.cap>0) continue;
int v=edges[G[x][i]^1].fr;
if(!vis[v]){
vis[v]=1;
d[v]=d[x]+1;
q.push(v);
}
}
}
}
int augment()
{
int a=INF;
for(int u=t;u!=s;u=edges[p[u]].fr){
Edge &e=edges[p[u]];
a=min(a,e.cap-e.fw);
}
for(int u=t;u!=s;u=edges[p[u]].fr){
edges[p[u]].fw+=a;
edges[p[u]^1].fw-=a;
}
return a;
}
int maxFlow(int s,int t)
{
this->s=s,this->t=t;
bfs(t);
int flow=0;
memset(gap,0,sizeof(gap));
for(int i=0;i<n;++i) ++gap[d[i]];
memset(cur,0,sizeof(cur));
int x=s;
while(d[s]<n)
{
if(x==t){
flow+=augment();
x=s;
}
int flag=false;
for(int i=cur[x];i<G[x].size();++i){
Edge &e=edges[G[x][i]];
if(e.cap>e.fw&&d[x]==d[e.to]+1){
flag=true;
p[e.to]=G[x][i];
cur[x]=i;
x=e.to;
break;
}
}
if(!flag){
int m=n-1;
for(int i=0;i<G[x].size();++i){
Edge &e=edges[G[x][i]];
if(e.cap>e.fw) m=min(m,d[e.to]);
}
if((--gap[d[x]])==0) break;
d[x]=m+1;
++gap[d[x]];
cur[x]=0;
if(x!=s) x=edges[p[x]].fr;
}
}
return flow;
}
};
ISAP solver;
int d,f,b;
int dd[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
bool ok(int x,int y)
{
return x>=1&&x<=n&&y>=1&&y<=m;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int cnt=0;
scanf("%d%d",&m,&n);
scanf("%d%d%d",&d,&f,&b);
for(int i=1;i<=n;++i){
scanf("%s",p[i]+1);
if(p[i][1]=='.'){
++cnt;
p[i][1]='#';
}
if(m>1&&p[i][m]=='.'){
++cnt;
p[i][m]='#';
}
if(i==1||i==n)
for(int j=1;j<=m;++j)
if(p[i][j]=='.'){
++cnt;
p[i][j]='#';
}
}
solver.init(n*m+2);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
for(int k=0;k<4;++k){
int ni=i+dd[k][0],nj=j+dd[k][1];
if(ok(ni,nj)) solver.addEdge((i-1)*m+j,(ni-1)*m+nj,b);
}
if(p[i][j]=='#'){
if(i==1||i==n||j==1||j==m)
solver.addEdge(0,(i-1)*m+j,INF);
else
solver.addEdge(0,(i-1)*m+j,d);
}else{
solver.addEdge((i-1)*m+j,n*m+1,f);
}
}
}
printf("%d
",solver.maxFlow(0,n*m+1)+cnt*f);
}
return 0;
}