[SCOI2007]蜥蜴

题意

丢个链接就跑 https://www.luogu.org/problemnew/show/P2472

题解

先把每个点分为入和出，另有超级源点S，超级汇点T

然后建图

    1.每个柱子入向出连流量为高度的边
    2.初始有蜥蜴的柱子：S向入连边（流量为1）
    3.能跳出去的柱子：出向T连边（流量为inf）
    4.每个柱子的出向能跳得到的柱子的r连边（流量为inf）

调试记录

略

#include<queue>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f;
struct node{
    int nxt,to,weigh;
}edge[200100];
int level[100010];
int n,r,c,d,s,t,cnt=1,head[100010];
bool f[30][30];
char S[30];
std::queue<int>qu;
double dis(int x1,int y1,int x2,int y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void addedge(int x,int y,int z){
    edge[++cnt].nxt=head[x];
    edge[cnt].to=y;
    edge[cnt].weigh=z;
    head[x]=cnt;
}
bool bfs(){
    memset(level,-1,sizeof(level));
    level[s]=0;
    qu.push(s);
    while(!qu.empty()){
        int u=qu.front();
        qu.pop();
        for(int i=head[u];i;i=edge[i].nxt){
            int upup=edge[i].to;
            if(edge[i].weigh!=0 && level[upup]==-1){
                level[upup]=level[u]+1;
                qu.push(upup);
            }
        }
    }
    if(level[t]==-1)return false;
    else return true;
}
int dfs(int x,int flow){
    if(x==t)return flow;
    int rest=0;
    for(int i=head[x];i;i=edge[i].nxt){
        if(rest>=flow)break;
        int upup=edge[i].to;
        if(level[upup]==level[x]+1){
            int sum=dfs(upup,std::min(flow-rest,edge[i].weigh));
            rest+=sum,edge[i].weigh-=sum,edge[i^1].weigh+=sum;
        }
    }
    return rest;
}
int Dinic(int s,int t){
    int ans=0;
    while(bfs())
        ans+=dfs(s,inf);
    return ans;
}
int main(){
    scanf("%d%d%d",&r,&c,&d);
    s=0,t=2*r*c+1;
    for(int i=1;i<=r;i++){
        scanf("%s",&S);
        for(int j=0;j<c;j++)
            if(S[j]!='0'){
                f[i][j+1]=true;
                addedge(2*((i-1)*c+j)+1,2*((i-1)*c+j)+2,S[j]-'0');
                addedge(2*((i-1)*c+j)+2,2*((i-1)*c+j)+1,0);
            }
    }
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++){
            if(!f[i][j])continue;
            for(int x1=max(1,i-d);x1<=min(r,i+d);x1++)
                 for(int y1=max(1,j-d);y1<=min(c,j+d);y1++)
                     if(dis(x1,y1,i,j)<=d && f[x1][y1] && (i!=x1 || j!=y1)){
                         addedge(2*((i-1)*c+j-1)+2,2*((x1-1)*c+y1-1)+1,inf);
                         addedge(2*((x1-1)*c+y1-1)+1,2*((i-1)*c+j-1)+2,0);
                     }
            if(i<=d || j<=d || (r-i+1)<=d || (c-j+1)<=d){
                addedge(2*((i-1)*c+j-1)+2,t,inf);
                addedge(t,2*((i-1)*c+j-1)+2,0);
            }
        }
    for(int i=1;i<=r;i++){
        scanf("%s",&S);
        for(int j=0;j<c;j++){
            if(S[j]=='L'){
                n++;
                addedge(s,2*((i-1)*c+j)+1,1);
                addedge(2*((i-1)*c+j)+2,s,0);
            }
        }
    }
    printf("%d\n",n-Dinic(s,t));
    return 0;
}