hdu2732

题解：

和上一题差不多

然后注意格式

代码：

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

const int N=;

using namespace std;

struct data{int to,ne,v;}e[];

int r,c,d,T,cnt,ans,cas,mp[N][N],mark[N][N],q[],h[],fi[];

void ins(int u,int v,int w)

{

    cnt++;e[cnt].to=v;

    e[cnt].ne=fi[u];

    fi[u]=cnt;

    e[cnt].v=w;

}

void insert(int u,int v,int w)

{

    ins(u,v,w);

    ins(v,u,);

}

int judge(int x1,int y1,int x2,int y2)

{

    if (((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))<=(d*d)&&mp[x1][y1]&&mp[x2][y2])

     return ;

    return ;

}

void build()

{

    for (int x1=;x1<=r;x1++)

     for (int y1=;y1<=c;y1++)

      for (int x2=x1-d;x2<=x1+d;x2++)

       for (int y2=y1-d;y2<=y1+d;y2++)

    if (judge(x1,y1,x2,y2)&&(x1!=x2||y1!=y2))

     insert(mark[x1][y1]+,mark[x2][y2],1e9);

    for (int i=;i<=r;i++)

     for (int j=;j<=c;j++)

      if (mp[i][j])insert(mark[i][j],mark[i][j]+,mp[i][j]);

}

int bfs()

{

    memset(h,-,sizeof(h));

    int t=,w=,now;

    q[]=h[]=;

    while (t<w)

     {

        now=q[t++];

        for (int i=fi[now];i;i=e[i].ne)

         if (e[i].v&&h[e[i].to]==-)

          {

            h[e[i].to]=h[now]+;

            q[w++]=e[i].to;

          }

     }

    if (h[]==-)return ;

    return ;

}

int dfs(int x,int f)

{

    if (x==)return f;

    int used=,w;

    for (int i=fi[x];i;i=e[i].ne)

     if (e[i].v&&h[e[i].to]==h[x]+)

      {

        w=f-used;w=dfs(e[i].to,min(w,e[i].v));

        e[i].v-=w;e[i^].v+=w;

        used+=w;

        if(used==f)return f;

      }

    if (!used)h[x]=-;

    return used;

}

void doit()

{

    scanf("%d%d",&r,&d);

    char ch[N];

    memset(mp,,sizeof mp);

    memset(mark,,sizeof mark);

    memset(fi,,sizeof fi);

    memset(e,,sizeof e);

    memset(q,,sizeof q);

    memset(h,,sizeof h);

    cnt=;

    ans=;

    for (int i=;i<=r;i++)

     {

           scanf("%s",ch);

           c=strlen(ch);

           for (int j=;j<=c;j++)mp[i][j]=ch[j-]-'';

     }

    int tot=;

    for (int i=;i<=r;i++)

     for (int j=;j<=c;j++)

      {

          tot++;

        mark[i][j]=tot;

       }

    for (int i=;i<=r;i++)

     {

           scanf("%s",ch);

           for (int j=;j<=c;j++)

         if (ch[j-]=='L'){insert(,mark[i][j],);ans++;}

     }

    for (int i=;i<=d;i++)

     for (int j=d+;j<=r-d;j++)

      {

        insert(mark[j][i]+,,1e9);

        insert(mark[j][c-i+]+,,1e9);

      }

    for (int i=;i<=d;i++)

     for (int j=;j<=c;j++)

      {

        insert(mark[i][j]+,,1e9);

        insert(mark[r-i+][j]+,,1e9);

      }

    build();

    while (bfs())ans-=dfs(,1e9);

    printf("Case #%d: ",++cas);

    if (ans==)printf("no ");else printf("%d ",ans);

     if (ans<)puts("lizard was left behind.");

    else puts("lizards were left behind.");

}

int main()

{

    scanf("%d",&T);

    while (T--)doit();

}