构图……
拆点,每根石柱拆成两个点,一个入一个出,两点间容量为石柱的高度
AC-Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXMAP=25,INF=43456344;//INF still by RANDOM
//--邻接表
struct Edge{int t,v,op,next;}E[MAXMAP*MAXMAP*200];//位置及容量和反向边
int pStart[MAXMAP*MAXMAP*100];//
//--路径
bool vis[MAXMAP*MAXMAP*100];
int pE[MAXMAP*MAXMAP*100],pP[MAXMAP*MAXMAP*100];
//--题干
int R,C,D;
int totE=0;
//--
int S=0,T;
int totT;
inline int GetPN(int x,int y,int l)
{
return ((x*21+y)*2)+l;
}
void Spfa()
{
int u;
memset(vis,0,sizeof(vis));
memset(pE,-1,sizeof(pE));
memset(pP,-1,sizeof(pP));
queue<int>Q;
Q.push(S);
vis[S]=true;
while (!Q.empty())
{
u=Q.front();Q.pop();
for (int up=pStart[u];up;up=E[up].next)
if (E[up].v>0&&!vis[E[up].t])
{
vis[E[up].t]=true;
pE[E[up].t]=up;
pP[E[up].t]=u;
Q.push(E[up].t);
}
}
}
int MaxFlow()
{
int ret=0,tret,u;
while (1)
{
Spfa();
if (!vis[T])
break;
tret=0x3f3f3f3f;
for (u=T;pP[u]!=-1;u=pP[u])
tret=min(tret,E[pE[u]].v);
for (u=T;pP[u]!=-1;u=pP[u])
{
E[pE[u]].v-=tret;
E[E[pE[u]].op].v+=tret;
}
ret+=tret;
}
return ret;
}
void AddEdge(int u,int v,int c)
{
int E1=++totE;
int E2=++totE;
E[E1].t=v;E[E1].v=c;E[E1].op=E2;E[E1].next=pStart[u];pStart[u]=E1;
E[E2].t=u;E[E2].v=0;E[E2].op=E1;E[E2].next=pStart[v];pStart[v]=E2;
}
bool Dis(int x1,int y1,int x2,int y2)
{
return ((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))<=D*D;
}
int main()
{
char tmp;
cin>>R>>C>>D;
for (int i=1;i<=R;i++)
for (int j=1;j<=C;j++)
for (int k=1;k<=R;k++)
for (int l=1;l<=C;l++)
if ((i!=k||j!=l)&&Dis(i,j,k,l))
AddEdge(GetPN(i,j,1),GetPN(k,l,0),INF);
for (int i=1;i<=R;i++)
for (int j=1;j<=C;j++)
{
cin>>tmp;
if (tmp!='0')
AddEdge(GetPN(i,j,0),GetPN(i,j,1),tmp-'0');
}
for (int i=1;i<=R;i++)
for (int j=1;j<=C;j++)
{
cin>>tmp;
if (tmp=='L')
{
totT++;
AddEdge(S,GetPN(i,j,0),1);
}
}
T=GetPN(R+2,C+2,0);
for (int i=1;i<=R;i++)
for (int j=1;j<=C;j++)
if (Dis(i,j,i,0)||Dis(i,j,0,j)||Dis(i,j,i,C+1)||Dis(i,j,R+1,j))
AddEdge(GetPN(i,j,1),T,INF);
cout<<totT-MaxFlow()<<endl;
return 0;
}