1 条题解

  • 1
    @ 2022-9-5 18:16:33
    #include<cstdio>
    #include<algorithm>
    #include<queue>
    #include<cstring>
    using namespace std;
    queue <int> q;
    const int maxn=807;
    const int maxm=100007;
    const int inf=0x7f7f7f7f;
    struct E{
    	int u,v,cf;
    }e[maxm];//cf是指流量
    #define cf(i) e[i].cf
    int first[maxn],nt[maxm],ES=1;
    inline void addE(int u,int v,int cf)
    {
    	e[++ES]=(E){u,v,cf};
    	nt[ES]=first[u];
    	first[u]=ES;
    	return ;
    }
    inline void add(int u,int v,int cf)//网络瘤专用加双边
    {
    	addE(u,v,cf);addE(v,u,0);
    	return ;
    }
    int N,M,S,T;
    char m1[27][27],m2[27][27];
    inline int num(int i,int j)//根据一个点的坐标得到其入点编号
    {
    	return (i-1)*M+j;
    }
    int d,all,ans;
    inline void linkE(int u,int i,int j)//从编号u连向 (i,j)
    {
    	if(i<1||i>N||j<1||j>M)//落在图外直接连到T
    	{
    		add(u,T,inf);
    		return ;
    	}
    	if(m1[i][j]=='0') return ;
    	add(u,num(i,j),inf);
    	return ;
    }
    inline void link(int i,int j)//点(i,j)连边
    {
    	if(m1[i][j]=='0') return ; 
    	add(num(i,j),num(i,j)+all,m1[i][j]-'0');
    	if(m2[i][j]=='L')
    		add(S,num(i,j),1),ans++;//是蜥蜴,顺便统计蜥蜴只数
    	if(i==1||j==1||i==N||j==M)
    		add(num(i,j)+all,T,inf);
    	int u=num(i,j)+all;
        //最没营养的一部分
    	if(d>=1)
    	{
    		linkE(u,i-1,j);linkE(u,i+1,j);
    		linkE(u,i,j-1);linkE(u,i,j+1);
    	}
    	if(d>=2)
    	{
    		linkE(u,i-2,j);linkE(u,i+2,j);
    		linkE(u,i,j-2);linkE(u,i,j+2);
    		linkE(u,i-1,j-1);linkE(u,i-1,j+1);
    		linkE(u,i+1,j-1);linkE(u,i+1,j+1);
    	}
    	if(d>=3)
    	{
    		linkE(u,i-3,j);linkE(u,i+3,j);linkE(u,i,j-3);linkE(u,i,j+3);
    		linkE(u,i-2,j-2);linkE(u,i-2,j+2);linkE(u,i+2,j-2);linkE(u,i+2,j+2);
    		linkE(u,i-1,j-2);linkE(u,i-1,j+2);linkE(u,i+1,j-2);linkE(u,i+1,j+2);
    		linkE(u,i-2,j-1);linkE(u,i-2,j+1);linkE(u,i+2,j-1);linkE(u,i+2,j+1);
    	}
    	if(d>=4)
    	{
    		linkE(u,i-4,j);linkE(u,i+4,j);linkE(u,i,j-4);linkE(u,i,j+4);
    		linkE(u,i-1,j-3);linkE(u,i-1,j+3);linkE(u,i+1,j-3);linkE(u,i+1,j+3);
    		linkE(u,i-3,j-1);linkE(u,i-3,j+1);linkE(u,i+3,j-1);linkE(u,i+3,j+1);
    		linkE(u,i-3,j-2);linkE(u,i-3,j+2);linkE(u,i+3,j-2);linkE(u,i+3,j+2);
    		linkE(u,i-2,j-3);linkE(u,i-2,j+3);linkE(u,i+2,j-3);linkE(u,i+2,j+3);
    	}
       //呜呜终于写完了
    	return ;
    }
    //Dinic最大流部分
    int cur[maxn],cnt[maxn];
    inline bool BFS()
    {
    	memset(cnt,0,sizeof(cnt));
    	cnt[S]=1;
    	q.push(S);
    	int u,v;
    	while(!q.empty())
    	{
    		u=q.front();q.pop();
    		for(register int i=first[u];i;i=nt[i])
    		{
    			v=e[i].v;
    			if(cf(i)>0&&!cnt[v])
    			{
    				cnt[v]=cnt[u]+1;
    				q.push(v);
    			}
    		}
    	}
    	return cnt[T]!=0;
    }
    inline int dfs(int u,int f)
    {
    	if(u==T) return f;
    	int d,v,sum=0;
    	for(register int &i=cur[u];i;i=nt[i])//cur数组是 当前弧优化
    	{
    		v=e[i].v;
    		if(cf(i)>0&&cnt[v]==cnt[u]+1)
    		{
    			d=dfs(v,min(f,cf(i)));
    			if(d>0)
    			{
    				f-=d;sum+=d;
    				cf(i)-=d;cf(i^1)+=d;
    				if(f<=0) return sum;
    			}
    		}
    	}
    	return sum;
    }
    int main()
    {
    	scanf("%d%d%d",&N,&M,&d);
        T=N*M*2+1;all=N*M;//入点编号为u的点的出点为u+all
    	for(register int i=1;i<=N;i++)
    		scanf("%s",m1[i]+1);
    	for(register int i=1;i<=N;i++)
    		scanf("%s",m2[i]+1);
    	for(register int i=1;i<=N;i++)
    		for(register int j=1;j<=M;j++)
    			link(i,j);
    	while(BFS())
    	{
    		memcpy(cur,first,sizeof(cur));
    		ans-=dfs(S,inf);//流量都是跑出去的蜥蜴,要求剩下的蜥蜴。
           //在连边函数里面已经统计了蜥蜴数量,减去就可以
    	}
    	printf("%d",ans);
    	return 0;
    }
    
    • 1

    信息

    ID
    1066
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    (无)
    递交数
    41
    已通过
    22
    上传者