解题:SCOI 2007 蜥蜴

题面

拆点跑最大流

所有能跑出去的点连向汇点，容量为inf

原点连向所有初始有蜥蜴的点，容量为1

每根柱子拆成两个点“入口”和“出口”，入口向出口连容量为高度的边，出口向别的有高度的柱子的入口连容量为高度的边

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=,M=,inf=1e9;

 int n,m,d,f,b,s,t,t1,t2,t3,cnt,tot,ans;

 int p[N],pp[N],dep[N],que[N],idx[N][N];

 int noww[M],goal[M],flow[M];

 char mapp[N][N];

 void Link(int f,int t,int v)

 {

     noww[++cnt]=p[f],p[f]=cnt;

     goal[cnt]=t,flow[cnt]=v;

     noww[++cnt]=p[t],p[t]=cnt;

     goal[cnt]=f,flow[cnt]=;

 }

 int Dis(int a,int b,int c,int d)

 {

     return (a-c)*(a-c)+(b-d)*(b-d);

 }

 void Init(int st,int ed)

 {

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

         pp[i]=p[i],dep[i]=-;

     dep[st]=,que[f=b=]=st;

 }

 bool Layering(int st,int ed)

 {

     Init(st,ed);

     while(f<=b)

     {

         int tn=que[f++];

         for(int i=pp[tn];i;i=noww[i])

             if(dep[goal[i]]==-&&flow[i])

                 dep[goal[i]]=dep[tn]+,que[++b]=goal[i];

     }

     return ~dep[ed];

 }

 int Augmenting(int nd,int ed,int mn)

 {

     if(nd==ed||!mn) return mn;

     int tmp=,tep=;

     for(int i=pp[nd];i;i=noww[i])

     {

         pp[nd]=i;

         if(dep[goal[i]]==dep[nd]+)

             if(tep=Augmenting(goal[i],ed,min(mn,flow[i])))

             {

                 flow[i]-=tep,mn-=tep;

                 flow[i^]+=tep,tmp+=tep;

                 if(!mn) break;

             }

     }

     return tmp;

 }

 int Dinic_Maxflow(int st,int ed)

 {

     int ret=;

     while(Layering(st,ed))

         ret+=Augmenting(st,ed,inf);

     return ret;

 }

 int main ()

 {

     scanf("%d%d%d",&n,&m,&d);

     s=*n*m+,t=s+,cnt=;

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

     {

         scanf("%s",mapp[i]+);

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

             idx[i][j]=++tot;

     }

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

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

             if(mapp[i][j]!='')

             {

                 Link(idx[i][j],idx[i][j]+n*m,mapp[i][j]-'');

                 if(i-d<||i+d>n||j-d<||j+d>m)

                     Link(idx[i][j]+n*m,t,inf);

                 else

                     for(int k=;k<=n;k++)

                         for(int h=;h<=m;h++)

                             if(Dis(i,j,k,h)<=d*d&&(i!=k||j!=h)&&mapp[k][h]!='')

                                 Link(idx[i][j]+n*m,idx[k][h],mapp[i][j]-'');

             }

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

     {

         scanf("%s",mapp[i]+);

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

             if(mapp[i][j]=='L') ans++,Link(s,idx[i][j],);

     }

     printf("%d\n",ans-Dinic_Maxflow(s,t));

     return ;

 }