<span>网络流杂题二</span>

正解的思路并没有局限于原图中的网络流，而是将网格图黑白染色。

将源点向黑点建边，黑点向可以连接的白点建边，之后原图无缝拼接可以简单地转化为跑最大流之后能够满流。

所以只要考虑如何加入翻转次数的限制。

因为流量必须全部流向同一个状态，简单拆分为四个方向似乎并不是可行的。

题解是将每个点拆分为四个点，分别连接对应的四个方向相邻的点，所以分类讨论：

对于四元管或无管，翻转无意义。

对于直线，题中规定不可翻转。

对于单元管，直接连上三个方向，费用分别为1 2 1就好了。

L型管和T型管比较复杂，可以直接参考代码，

思想大概是通过一些奇怪的建图，在保持原形态不变的意义下，满足翻转次数恰好与消耗费用形成匹配的关系。

因为懒得想，所以代码可以直接分类讨论

#include<bits/stdc++.h>
using namespace std;
const int N=2020;
int n,m,s,t,tot=1,sum,f;
int dis[N<<2],head[N<<2],inq[N<<2],pre[N<<2],to[N<<4],nxt[N<<4],w[N<<4],val[N<<4];
inline bool spfa(){
	queue<int> q; q.push(s);
	memset(dis,0x3f,sizeof(dis)); dis[s]=0;
	while(!q.empty()){
		int x=q.front(); q.pop(); inq[x]=0;
		for(int i=head[x];i;i=nxt[i]) if(w[i]&&dis[x]+val[i]<dis[to[i]]){
			dis[to[i]]=dis[x]+val[i];
			pre[to[i]]=i;
			if(!inq[to[i]]) inq[to[i]]=1,q.push(to[i]);
		}
	}
	return dis[t]!=dis[0];
}
inline void add(int a,int b,int flow,int co){
	nxt[++tot]=head[a]; to[head[a]=tot]=b; w[tot]=flow; val[tot]=co;
	nxt[++tot]=head[b]; to[head[b]=tot]=a; val[tot]=-co;
}
inline void Add(int a,int b,int flow,int co){
	add(b,a,flow,co);
}
inline int id(int x,int y,int cpy){
	return (cpy-1)*n*m+(x-1)*m+y;
}
inline int read(register int x=0,register char ch=getchar(),register int f=0){
	for(;!isdigit(ch);ch=getchar()) f=ch=='-';
	for(; isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
	return f?-x:x;
}
int main(){
	n=read(); m=read(); s=n*m*4+1; t=s+1;
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){//上 右 下 左
		int k=read();
		if(i+j&1){
			if(k&1) ++sum,add(s,id(i,j,1),1,0);
			if(k&2) ++sum,add(s,id(i,j,2),1,0);
			if(k&4) ++sum,add(s,id(i,j,3),1,0);
			if(k&8) ++sum,add(s,id(i,j,4),1,0);
			if(j!=1) add(id(i,j,4),id(i,j-1,2),1,0);
			if(j!=m) add(id(i,j,2),id(i,j+1,4),1,0);
			if(i!=1) add(id(i,j,1),id(i-1,j,3),1,0);
			if(i!=n) add(id(i,j,3),id(i+1,j,1),1,0);
			switch(k){
				case 0:break;
				case 1:add(id(i,j,1),id(i,j,2),1,1);add(id(i,j,1),id(i,j,3),1,2);add(id(i,j,1),id(i,j,4),1,1);break;
				case 2:add(id(i,j,2),id(i,j,1),1,1);add(id(i,j,2),id(i,j,3),1,1);add(id(i,j,2),id(i,j,4),1,2);break;
				case 3:add(id(i,j,1),id(i,j,3),1,1);add(id(i,j,2),id(i,j,4),1,1);break;
				case 4:add(id(i,j,3),id(i,j,1),1,2);add(id(i,j,3),id(i,j,2),1,1);add(id(i,j,3),id(i,j,4),1,1);break;
				case 5:break;//直线
				case 6:add(id(i,j,2),id(i,j,4),1,1);add(id(i,j,3),id(i,j,1),1,1);break;
				case 7:add(id(i,j,1),id(i,j,2),1,1);add(id(i,j,2),id(i,j,3),1,1);add(id(i,j,3),id(i,j,4),1,1);add(id(i,j,1),id(i,j,4),1,1);break;
				case 8:add(id(i,j,4),id(i,j,1),1,1);add(id(i,j,4),id(i,j,2),1,2);add(id(i,j,4),id(i,j,3),1,1);break;
				case 9:add(id(i,j,1),id(i,j,3),1,1);add(id(i,j,4),id(i,j,2),1,1);break;
				case 10:break;//直线
				case 11:add(id(i,j,4),id(i,j,1),1,1);add(id(i,j,1),id(i,j,2),1,1);add(id(i,j,2),id(i,j,3),1,1);add(id(i,j,4),id(i,j,3),1,1);break;
				case 12:add(id(i,j,4),id(i,j,2),1,1);add(id(i,j,3),id(i,j,1),1,1);break;
				case 13:add(id(i,j,3),id(i,j,4),1,1);add(id(i,j,4),id(i,j,1),1,1);add(id(i,j,1),id(i,j,2),1,1);add(id(i,j,3),id(i,j,2),1,1);break;
				case 14:add(id(i,j,2),id(i,j,3),1,1);add(id(i,j,3),id(i,j,4),1,1);add(id(i,j,4),id(i,j,1),1,1);add(id(i,j,2),id(i,j,1),1,1);break;
				case 15:break;//完全
			}
		}
		else{
			if(k&1) add(id(i,j,1),t,1,0),++f;
			if(k&2) add(id(i,j,2),t,1,0),++f;
			if(k&4) add(id(i,j,3),t,1,0),++f;
			if(k&8) add(id(i,j,4),t,1,0),++f;
			switch(k){
				case 0:break;
				case 1:Add(id(i,j,1),id(i,j,2),1,1);Add(id(i,j,1),id(i,j,3),1,2);Add(id(i,j,1),id(i,j,4),1,1);break;
				case 2:Add(id(i,j,2),id(i,j,1),1,1);Add(id(i,j,2),id(i,j,3),1,1);Add(id(i,j,2),id(i,j,4),1,2);break;
				case 3:Add(id(i,j,1),id(i,j,3),1,1);Add(id(i,j,2),id(i,j,4),1,1);break;
				case 4:Add(id(i,j,3),id(i,j,1),1,2);Add(id(i,j,3),id(i,j,2),1,1);Add(id(i,j,3),id(i,j,4),1,1);break;
				case 5:break;//直线
				case 6:Add(id(i,j,2),id(i,j,4),1,1);Add(id(i,j,3),id(i,j,1),1,1);break;
				case 7:Add(id(i,j,1),id(i,j,2),1,1);Add(id(i,j,2),id(i,j,3),1,1);Add(id(i,j,3),id(i,j,4),1,1);Add(id(i,j,1),id(i,j,4),1,1);break;
				case 8:Add(id(i,j,4),id(i,j,1),1,1);Add(id(i,j,4),id(i,j,2),1,2);Add(id(i,j,4),id(i,j,3),1,1);break;
				case 9:Add(id(i,j,1),id(i,j,3),1,1);Add(id(i,j,4),id(i,j,2),1,1);break;
				case 10:break;//直线
				case 11:Add(id(i,j,4),id(i,j,1),1,1);Add(id(i,j,1),id(i,j,2),1,1);Add(id(i,j,2),id(i,j,3),1,1);Add(id(i,j,4),id(i,j,3),1,1);break;
				case 12:Add(id(i,j,4),id(i,j,2),1,1);Add(id(i,j,3),id(i,j,1),1,1);break;
				case 13:Add(id(i,j,3),id(i,j,4),1,1);Add(id(i,j,4),id(i,j,1),1,1);Add(id(i,j,1),id(i,j,2),1,1);Add(id(i,j,3),id(i,j,2),1,1);break;
				case 14:Add(id(i,j,2),id(i,j,3),1,1);Add(id(i,j,3),id(i,j,4),1,1);Add(id(i,j,4),id(i,j,1),1,1);Add(id(i,j,2),id(i,j,1),1,1);break;
				case 15:break;//完全
			}
		}
	}
	int ans=0,flow=0;
	while(spfa()){
		int x=t; ans+=dis[t]; ++flow;
		while(x!=s) --w[pre[x]],++w[pre[x]^1],x=to[pre[x]^1];
	}
	printf("%d\n",flow==sum&&f==sum?ans:-1);
	return 0;
}

似乎可以用上下界做，将每个点拆为两个点以限制点的流量。

然后发现这个东西可能会出现负环，所以就很难搞。

因为原图中不考虑穿越一定为拓扑图，然而穿越有一个特殊的性质。

只要每个点连到终点，之后从起点连到任意一个点，边权为穿越的权值就好了。

所以现在的一个流量，对应的是两次使用穿越之间的路程。将这个东西跑一个最小可行流。

正解用的是另一个拆点方法，将每个点拆为出点/入点。

源点向每个出点，连边流量1，费用0。

源点向每个入点，连边流量1，费用为穿越费用。

入点向汇点，连边流量1，费用0。

原图中的边，出点向入点，流量为1，费用为对应费用。

因为走到一个点对应一个流量，为了满足最大流一定满流。

因为源点向出点的流量为1，那么满足每个点的出入度是守恒的。

对于穿越的情况，同样是利用了与穿越之前点无关的性质，重新回到起点穿越。

类似于《数字配对》。

该题的方法同样是分为左部点和右部点。

考虑奇数和偶数。

偶数与偶数的$gcd$一定不为1。

奇数与奇数一定不可以组成平方数，在$mod\ 4$的同余系下考虑就可以证明。

所以直接费用流就好了。

几个中选至少一个的问题，显然串联之后用割解决。

然而发现这个图似乎并不是很好连，因为串联过程中如果出现不想要的限制就会完戏。

似乎一个简单的做法是四色染色，这个时候就要翻右侧友链去看DC大神题解。

然而我会盗图，所以不用去了。

观察即可发现所有的串联关系都表示为ABCD，然后就完事了。

然而一个从没看到过四色染色的人是很难想到这个玩意的。

但是疯狂手玩样例，可以想到将特殊边分为两类，然后对于第一类从左到右串联，第二类从右到左串联。

这样通过交叉点在网络流的同一侧，有效规避了不想要的串联效果。

化一化式子，就发现这个玩意有点像最大权闭合子图。

两个点都选对应一个收益。

所以新建$n^2$个点，随便连一些$inf$边就好了。

然而显然这个做法的复杂度并不对。

所以套用《employ人员雇佣》的做法就好了。

一个结论是原图中最小的海拔分布一定为0 1分别成联通块。

所以这个玩意就是一个最小割。

因为原图为对偶图，所以画一画图就可以发现，

正向边对应正向割边的边权，反向边对应反向割边的边权，直接转完对偶图跑最短路就好了。

网络流杂题二

A. 无限之环

B. 星际竞速

C. bzoj3158千钧一发

D. 4823: 老C的方块

F. 线性代数

H. 2007: 海拔