Luogu4003 无限之环 | Arahc's Home

题面

简化题意

给定一个 $n\times m$ 的网格，网格有水管。不能旋转直线管道，求最少旋转多少次管道使其闭环，或判断无解。一次旋转只能旋转 $90^\circ$ 。

$nm\leq 2000$ 。注意不是 $n,m\leq 2000$ 。

题解

下文的配图全部来自原题的图，拆解出每个管子之后在 Excel 里面拼起来。很多接口可能没对齐 QAQ。

不会旋转

我们先来考虑一个不会漏水的情况：

（为什么画一个这个图？它好就好在所有样式的管子都用过……）

然后你会发现很难有什么思路。但是如果考虑网络流，不难得到所谓“不会漏水”的条件，可以转化为一个满流的问题，即每个水管（的分支口）容量都为 $1$ ，最终要保证满流。

于是我们先考虑如何对一个不需要旋转的图建模，使得这个图的每个水管的支口满流。可以考虑拆点，如果你和我一样 naive 地把一个点拆成上下左右四个，你发现是完全不可行的。于是我们把一个点拆成：上、下、左、右、中五个点。其中上、下、左、右是“连接点”，负责和别的格子相连，中间点是“主要点”，负责接口源/汇点，并根据水管形状向连接点连边。

然后考虑如何定向、如何分布源汇点，考虑将格子黑白染色，黑色格子由源点连向其主要点，白色格子的主要点连向其汇点。就可以保证最大流下接口都有流量了。

于是关于上面这个图，我们可以得到下面的建边：

当然这里忽略了一些没有用到的连接点，而且相邻两个点的重合的连接点只画了一个……这都是代码实现的细节，这张图足以解释问题。

将源点连接到所有的紫色点，容量为无限；将所有黄色点连接到汇点，容量为无限；所有图中的黑色边容量为 $1$ 。那么这张图的最大流就是每个接口满流的。

怎么转

注意到十字形的管道转不转都是一样的，所以不需要考虑十字形管道怎么转。还要注意题面中写到了直线型管道不能转。

因此，我们把这个图改造一下，分别考虑如何旋转 Q 型、T 型、L 型管道。

因为“流量”已经用来判是否满流（有解）了，因此我们只能加一个“费用”来代表旋转次数。

可以明确的是，当前图上所有的边（黑色边、源/汇点与紫/黄色点的连边）费用都是 $0$ 。这是不需要旋转就能得到的局面。

另外，因为同种类的水管，连边方式是等价的。因此在本文中我们只讨论按照上面这个图里被打乱的方向考虑。对于同类型、不同方向的水管，转一下就可以了，本质是一样的。当然还要注意连边方向和黑白染色对应的颜色有关。

例如上图，我们应该要加入一些有费用的边（下图中橙色的边），使其变为一个能满流的图。不难发现应该是如下的情况：

然后就对着这个图开始分讨吧 =.=

Q 型

见上图中第三行第三列，我们以朝上的 Q 型水管为例子讨论。

因为只有一个接口，这很好做。往左、往右都是旋转一次，往下需要旋转两次。因此从上连接点向左、右连接点连接流量 $1$ ，费用 $1$ 的边；向下连接点连接流量 $1$ ，费用 $2$ 的边。

L 型

见上图中第一行第四列，我们以连接右、下两个两个方向的 L 型水管为例子讨论。

我们考虑将其旋转为连接左、下两个方向的水管，可以视为下面的水管没动，把右边的水管接到左边来。而旋转到右、上方向同理。因此从右连接点向左连接点连流量 $1$ ，费用 $1$ 的边，下连接点向上连接点连流量 $1$ ，费用 $1$ 的边。

如果要旋转到左、上方向？相当于下面的水管接到上面、右边的水管接到左边。恰好是上述两个连边方向的总和，不需要额外考虑。

T 型

见上图第而行第一列，我们以下端没有接口的 T 型水管为例子讨论。

如果要把它变成左端或右端没有接口的水管，只需要旋转一次就可以了；如果要变成上端没有接口的水管，则需要旋转两次。因此由下连接点向左、右连接点连流量 $1$ ，费用 $1$ 的边；向上连接点连流量 $1$ ，费用 $2$ 的边。

于是所有的情况都已经讨论完了，建完边之后，跑一遍最小费用最大流。若没有满流，则说明无解；否则旋转次数就是最小费用。

建模实在难写、情况真多……

代码

代码很长，酌情阅读。

我也是人傻常数大，开 O2 才能过……

#include<bits/stdc++.h>
using namespace std;
const int max_n=20004,max_m=500005,inf=1061109567;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
struct graph{
	int hd[max_n],nx[max_m*2],to[max_m*2],ln[max_m*2],cs[max_m*2],ct;
	graph(){ct=1;}
	inline void add(int u,int v,int w,int c,bool tp=1){
	    if(!tp) swap(u,v);
		nx[++ct]=hd[u],hd[u]=ct,to[ct]=v,ln[ct]=w,cs[ct]=c;
		nx[++ct]=hd[v],hd[v]=ct,to[ct]=u,ln[ct]=0,cs[ct]=-c;
	}
}e;

int n,m,S,T,all;

queue<int> q;
bool vis[max_n];
int fl[max_n],dis[max_n],pre[max_n],ls[max_n];
inline bool spfa(){
	memset(fl,0x3f,sizeof(fl)),q.push(S);
	memset(dis,0x3f,sizeof(dis)),dis[S]=0;
	memset(vis,0,sizeof(vis)),vis[S]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		vis[u]=0;
		for(register int i=e.hd[u];i;i=e.nx[i]){
			int v=e.to[i];
			if(dis[v]<=dis[u]+e.cs[i] || !e.ln[i]) continue;
			dis[v]=dis[u]+e.cs[i];
			fl[v]=min(fl[u],e.ln[i]),
			pre[v]=u,
			ls[v]=i;
			if(!vis[v]){
				vis[v]=1,
				q.push(v);
			}
		}
	}
	return dis[T]!=inf;
}
inline int ek(){
	int res=0,f=0;
	while(spfa()){
	    int pf=fl[T];
		res+=fl[T]*dis[T];
		for(register int i=T;i!=S;i=pre[i]){
			e.ln[ls[i]]-=fl[T],
			e.ln[ls[i]^1]+=fl[T];
		}
		f+=pf;
	}
	return (f*2==all?res:-1);
}

// ---------------- 以上是费用流板子 ----------------

inline int ID(int i,int j,int way){
    int p=(i-1)*m+j;
    if(!way) return p;     // centre
    if(way==1) return p+n*m; // up
    if(way==2) return p+n*m*2; // down
    if(way==3) return p+n*m*3; // left
    return p+n*m*4;            // right
}
inline char type(int x){ // 根据接口判断种类
    int res=0,cnt=0;
    bool hv[5]={0,0,0,0,0};
    while(x){
        hv[++cnt]=x&1;
        if(x&1) ++res;
        x>>=1;
    }
    if(res==1)
        return 'Q';
    if(res==2){
        if((hv[1] && hv[3]) || (hv[2] && hv[4]))
            return 'I';
        return 'L';
    }
    if(res==3)
        return 'T';
    if(res==4)
        return '+';
    return ' ';
}

signed main(){
    n=read(),m=read(),S=n*m*5+1,T=S+1;
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j){
            int X=read();
            if(!X)
                continue;
            bool p=((i+j)&1); // 这个格子的颜色。判断连边是否需要反向。
            if(p)
                e.add(S,ID(i,j,0),inf,0,1);
            else
                e.add(ID(i,j,0),T,inf,0,1);
            if(i>1)
                e.add(ID(i,j,1),ID(i-1,j,2),1,0,p);
            if(j>1)
                e.add(ID(i,j,3),ID(i,j-1,4),1,0,p);
            if(X&1)
                e.add(ID(i,j,0),ID(i,j,1),1,0,p),++all;
            if((X>>1)&1)
                e.add(ID(i,j,0),ID(i,j,4),1,0,p),++all;
            if((X>>2)&1)
                e.add(ID(i,j,0),ID(i,j,2),1,0,p),++all;
            if((X>>3)&1)
                e.add(ID(i,j,0),ID(i,j,3),1,0,p),++all;
            
// 以上是主要点向连接点连边、相邻格子的连接点连边（无费用的边）
// 以下是增补的边（有费用的边）
            
            char tp=type(X);
            if(tp=='I' || tp=='+' || tp==' ')
                continue;
            /*
            0 -> centre
            1 -> up
            2 -> down
            3 -> left
            4 -> right
            */
            if(tp=='Q'){
                if(X&1){
                    e.add(ID(i,j,1),ID(i,j,2),1,2,p),
                    e.add(ID(i,j,1),ID(i,j,3),1,1,p),
                    e.add(ID(i,j,1),ID(i,j,4),1,1,p);
                }
                if((X>>1)&1){
                    e.add(ID(i,j,4),ID(i,j,1),1,1,p),
                    e.add(ID(i,j,4),ID(i,j,2),1,1,p),
                    e.add(ID(i,j,4),ID(i,j,3),1,2,p);
                }
                if((X>>2)&1){
                    e.add(ID(i,j,2),ID(i,j,1),1,2,p),
                    e.add(ID(i,j,2),ID(i,j,3),1,1,p),
                    e.add(ID(i,j,2),ID(i,j,4),1,1,p);
                }
                if((X>>3)&1){
                    e.add(ID(i,j,3),ID(i,j,1),1,1,p),
                    e.add(ID(i,j,3),ID(i,j,2),1,1,p),
                    e.add(ID(i,j,3),ID(i,j,4),1,2,p);
                }
            }
            if(tp=='L'){
                for(register int k=1;k<=4;++k)
                    if((X>>(k-1))&1){
                        int u,v;
                        if(k==1) u=1,v=2;
                        if(k==2) u=4,v=3;
                        if(k==3) u=2,v=1;
                        if(k==4) u=3,v=4;
                        e.add(ID(i,j,u),ID(i,j,v),1,1,p);
                    }
            }
            if(tp=='T'){
                if(!(X&1)){
                    e.add(ID(i,j,2),ID(i,j,1),1,2,p),
                    e.add(ID(i,j,3),ID(i,j,1),1,1,p),
                    e.add(ID(i,j,4),ID(i,j,1),1,1,p);
                }
                if(!((X>>1)&1)){
                    e.add(ID(i,j,1),ID(i,j,4),1,1,p),
                    e.add(ID(i,j,2),ID(i,j,4),1,1,p),
                    e.add(ID(i,j,3),ID(i,j,4),1,2,p);
                }
                if(!((X>>2)&1)){
                    e.add(ID(i,j,1),ID(i,j,2),1,2,p),
                    e.add(ID(i,j,3),ID(i,j,2),1,1,p),
                    e.add(ID(i,j,4),ID(i,j,2),1,1,p);
                }
                if(!((X>>3)&1)){
                    e.add(ID(i,j,1),ID(i,j,3),1,1,p),
                    e.add(ID(i,j,2),ID(i,j,3),1,1,p),
                    e.add(ID(i,j,4),ID(i,j,3),1,2,p);
                }
            }
        }
    write(ek());
    return 0;
}