题目：https://www.lydsy.com/JudgeOnline/problem.php?id=5120
https://www.luogu.org/problemnew/show/P4003
神奇的费用流建图；
首先，网格图，相邻之间有关系，所以先二分染色一下；
然后发现问题就是染色后黑白点之间要完美匹配插头；
所以可以考虑把旋转通过带一些代价变成插头方向的变化；
把一个格子拆成上下左右四个点，分类讨论，连边即可；
然而一开始连边竟然写了100多行...然后T了；
看了看题解代码，突然悟到了一些压行的方式，于是把建图压成了40行；
但还是T了，于是又改来改去，还把题解的建图粘过来囧，然后WA了；
这250行左右的代码就是一下午的辛酸调试：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int const xn=1e5,xm=4e5,inf=1e9;//
int n,m,hd[xn],ct=,to[xm],nxt[xm],w[xn],c[xn];
int dis[xn],pre[xn],inc[xn],S,T;
bool vis[xn];
queue<int>q;
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
int Min(int x,int y){return x<y?x:y;}
void ade(int x,int y,int z,int f){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; w[ct]=z; c[ct]=f;}
void add(int x,int y,int z,int f){ade(x,y,z,f); ade(y,x,-z,);}
int d[],bin[];
int id(int x,int y,int k){return ((x-)*m+y-)*+k;}
inline int get(int x)
{
int ret=;
for(int i=;i<=;i++)
if(x&bin[i-])d[i]=,ret++; else d[i]=;
return ret;
}
inline int op(int x){if(x<=)return x+; return x-;}
inline bool ck(){return (d[]&&d[]&&!d[]&&!d[])||(d[]&&d[]&&!d[]&&!d[]);}
inline bool bfs()
{
for(int i=S;i<=T;i++)vis[i]=;
for(int i=S;i<=T;i++)dis[i]=inf;
dis[S]=; inc[S]=inf; vis[S]=; q.push(S);
while(q.size())
{
int x=q.front(); q.pop(); vis[x]=;
//printf("x=%d d=%d\n",x,dis[x]);
for(int i=hd[x],u;i;i=nxt[i])
if(dis[u=to[i]]>dis[x]+w[i]&&c[i])
{
//if(w[i]<0)printf("i=%d w=%d c=%d\n",i,w[i],c[i]);
dis[u]=dis[x]+w[i]; pre[u]=i;
inc[u]=Min(inc[x],c[i]);
if(!vis[u])vis[u]=,q.push(u);
}
}
//printf("dis[%d]=%d\n",T,dis[T]);
return dis[T]!=inf;
}
inline void up()
{
int x=T;
while(x!=S)
{
int i=pre[x];
c[i]-=inc[T]; c[i^]+=inc[T];
x=to[i^];
}
}
int main()
{
n=rd(); m=rd(); S=; T=n*m*+;
bin[]=; for(int i=;i<=;i++)bin[i]=(bin[i-]<<);
int goal=;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
{
int x=rd(),u=; int t=(((i+j)&)==);
for (int k=;k<=;k++)
{
int nw=id(i,j,k);
if (x&(<<(k-))) u++,t?add(S,nw,,):add(nw,T,,);
}
goal+=u;
if (x==||x==) continue;
if (u==||u==) for (int k=;k<=;k++) add(id(i,j,k),id(i,j,k+&),,),add(id(i,j,k+&),id(i,j,k),,);
if (u==)
{
add(id(i,j,),id(i,j,),,),add(id(i,j,),id(i,j,),,);
add(id(i,j,),id(i,j,),,),add(id(i,j,),id(i,j,),,);
}
}
if (goal&) {puts("-1");return ;}goal>>=;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
if (((i+j)&)==)
{
if (i>) add(id(i,j,),id(i-,j,),,);
if (j<m) add(id(i,j,),id(i,j+,),,);
if (i<n) add(id(i,j,),id(i+,j,),,);
if (j>) add(id(i,j,),id(i,j-,),,);
}
/*
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int x=rd(); int cnt=get(x); goal+=cnt;
bool t=(((i+j)&1)==0);
if(t){for(int k=1;k<=4;k++)if(d[k])add(S,id(i,j,k),0,1);}
else {for(int k=1;k<=4;k++)if(d[k])add(id(i,j,k),T,0,1);}
if(x==5||x==10)continue;
if(cnt==1)
{
int nw; for(int k=1;k<=4;k++)if(d[k]){nw=k; break;}
if(t){for(int k=1;k<=4;k++)if(!d[k])add(nw,id(i,j,k),(k==op(nw)?2:1),1);}
else {for(int k=1;k<=4;k++)if(!d[k])add(id(i,j,k),nw,(k==op(nw)?2:1),1);}
}
if(cnt==3)
{
int nw; for(int k=1;k<=4;k++)if(!d[k]){nw=k; break;}
if(t){for(int k=1;k<=4;k++)if(d[k])add(id(i,j,k),nw,(k==op(nw)?2:1),1);}
else {for(int k=1;k<=4;k++)if(d[k])add(nw,id(i,j,k),(k==op(nw)?2:1),1);}
}
if(cnt==2)
{
if(t){for(int k=1;k<=4;k++)if(d[k])add(id(i,j,k),id(i,j,op(k)),1,1);}
else {for(int k=1;k<=4;k++)if(d[k])add(id(i,j,op(k)),id(i,j,k),1,1);}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(((i+j)&1)==0)
{
if(i>1)add(id(i,j,1),id(i-1,j,3),0,1);
if(j<m)add(id(i,j,2),id(i,j+1,4),0,1);
if(i<n)add(id(i,j,3),id(i+1,j,1),0,1);
if(j>1)add(id(i,j,4),id(i,j-1,2),0,1);
}
*/
/*
if(((i+j)&1)==0)//black
{
if(!ck())//!straight
{
if(cnt==1)
{
for(int k=1;k<=4;k++)
if(d[k])
{
int nw=id(i,j,k); add(S,nw,0,1);
for(int l=1;l<=4;l++)
if(l==k)continue;
else if(l==op(k))add(nw,id(i,j,l),2,1);
else add(nw,id(i,j,l),1,1);
break;
}
}
else if(cnt==2)
{
for(int k=1;k<=4;k++)
if(d[k])
{
add(S,id(i,j,k),0,1);
add(id(i,j,k),id(i,j,op(k)),1,1);
}
}
else if(cnt==3)
{
for(int k=1;k<=4;k++)
if(d[k])add(S,id(i,j,k),0,1);
else
{
for(int l=1,nw=id(i,j,k);l<=4;l++)
if(l==k)continue;
else if(l==op(k))add(id(i,j,l),nw,2,1);
else add(id(i,j,l),nw,1,1);
}
}
else if(cnt==4)
for(int k=1;k<=4;k++)add(S,id(i,j,k),0,1);
if(i-1)add(id(i,j,1),id(i-1,j,3),0,1);
if(j<m)add(id(i,j,2),id(i,j+1,4),0,1);
if(i<n)add(id(i,j,3),id(i+1,j,1),0,1);
if(j-1)add(id(i,j,4),id(i,j-1,2),0,1);
}
else//straight
{
for(int k=1;k<=4;k++)
if(d[k])add(S,id(i,j,k),0,1);
if(i-1&&d[1])add(id(i,j,1),id(i-1,j,3),0,1);
if(j<m&&d[2])add(id(i,j,2),id(i,j+1,4),0,1);
if(i<n&&d[3])add(id(i,j,3),id(i+1,j,1),0,1);
if(j-1&&d[4])add(id(i,j,4),id(i,j-1,2),0,1);
}
}
else//white
{
if(!ck())//!straight
{
if(cnt==1)
{
for(int k=1;k<=4;k++)
if(d[k])
{
int nw=id(i,j,k); add(nw,T,0,1);
for(int l=1;l<=4;l++)
if(l==k)continue;
else if(l==op(k))add(id(i,j,l),nw,2,1);
else add(id(i,j,l),nw,1,1);
break;
}
}
else if(cnt==2)
{
for(int k=1;k<=4;k++)
if(d[k])
{
add(id(i,j,k),T,0,1);
add(id(i,j,op(k)),id(i,j,k),1,1);
}
}
else if(cnt==3)
{
for(int k=1;k<=4;k++)
if(d[k])add(id(i,j,k),T,0,1);
else
{
int nw=id(i,j,k);
for(int l=1;l<=4;l++)
if(l==k)continue;
else if(l==op(k))add(nw,id(i,j,l),2,1);
else add(nw,id(i,j,l),1,1);
}
}
else if(cnt==4)
for(int k=1;k<=4;k++)add(id(i,j,k),T,0,1);
}
else//straight
{
for(int k=1;k<=4;k++)
if(d[k])add(id(i,j,k),T,0,1);
}
}
}
*/
//if(goal&1){puts("-1"); return 0;} goal>>=1;
int ans=,flow=;
while(bfs())ans+=dis[T]*inc[T],flow+=inc[T],up();
if(flow==goal)printf("%d\n",ans);
else puts("-1");
return ;
}
囧
突然发现连边里 nw 和 id(i,j,nw) 不分了，改过来后竟然——就A了！
但是空间必须开 4e5？明明我一开始算的应该是 4e4 ...
然而这篇代码在洛谷上一交，全是TLE...似乎还应该写多路增广SPFA...
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int const xn=1e5,xm=4e5,inf=1e9;
int n,m,hd[xn],ct=,to[xm],nxt[xm],w[xn],c[xn];
int dis[xn],pre[xn],inc[xn],S,T;
bool vis[xn];
queue<int>q;
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
int Min(int x,int y){return x<y?x:y;}
void ade(int x,int y,int z,int f){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; w[ct]=z; c[ct]=f;}
void add(int x,int y,int z,int f){ade(x,y,z,f); ade(y,x,-z,);}
int d[],bin[];
int id(int x,int y,int k){return ((x-)*m+y-)*+k;}
inline int get(int x)
{
int ret=;
for(int i=;i<=;i++)
if(x&bin[i-])d[i]=,ret++; else d[i]=;
return ret;
}
inline int op(int x){if(x<=)return x+; return x-;}
inline bool ck(){return (d[]&&d[]&&!d[]&&!d[])||(d[]&&d[]&&!d[]&&!d[]);}
inline bool bfs()
{
for(int i=S;i<=T;i++)dis[i]=inf;
dis[S]=; inc[S]=inf; vis[S]=; q.push(S);
while(q.size())
{
int x=q.front(); q.pop(); vis[x]=;
for(int i=hd[x],u;i;i=nxt[i])
if(dis[u=to[i]]>dis[x]+w[i]&&c[i])
{
dis[u]=dis[x]+w[i]; pre[u]=i;
inc[u]=Min(inc[x],c[i]);
if(!vis[u])vis[u]=,q.push(u);
}
}
return dis[T]!=inf;
}
inline void up()
{
int x=T;
while(x!=S)
{
int i=pre[x];
c[i]-=inc[T]; c[i^]+=inc[T];
x=to[i^];
}
}
int main()
{
n=rd(); m=rd(); S=; T=n*m*+;
bin[]=; for(int i=;i<=;i++)bin[i]=(bin[i-]<<);
int goal=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
int x=rd(); int cnt=get(x); goal+=cnt;
bool t=(((i+j)&)==);
if(t){for(int k=;k<=;k++)if(d[k])add(S,id(i,j,k),,);}
else {for(int k=;k<=;k++)if(d[k])add(id(i,j,k),T,,);}
if(x==||x==)continue;
if(cnt==)
{
int nw; for(int k=;k<=;k++)if(d[k]){nw=k; break;}
if(t){for(int k=;k<=;k++)if(!d[k])add(id(i,j,nw),id(i,j,k),(k==op(nw)?:),);}//id(i,j,nw)!!
else {for(int k=;k<=;k++)if(!d[k])add(id(i,j,k),id(i,j,nw),(k==op(nw)?:),);}
}
if(cnt==)
{
int nw; for(int k=;k<=;k++)if(!d[k]){nw=k; break;}
if(t){for(int k=;k<=;k++)if(d[k])add(id(i,j,k),id(i,j,nw),(k==op(nw)?:),);}
else {for(int k=;k<=;k++)if(d[k])add(id(i,j,nw),id(i,j,k),(k==op(nw)?:),);}
}
if(cnt==)
{
if(t){for(int k=;k<=;k++)if(d[k])add(id(i,j,k),id(i,j,op(k)),,);}
else {for(int k=;k<=;k++)if(d[k])add(id(i,j,op(k)),id(i,j,k),,);}
}
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(((i+j)&)==)
{
if(i>)add(id(i,j,),id(i-,j,),,);
if(j<m)add(id(i,j,),id(i,j+,),,);
if(i<n)add(id(i,j,),id(i+,j,),,);
if(j>)add(id(i,j,),id(i,j-,),,);
}
if(goal&){puts("-1"); return ;} goal>>=;
int ans=,flow=;
while(bfs())ans+=dis[T]*inc[T],flow+=inc[T],up();
if(flow==goal)printf("%d\n",ans);
else puts("-1");
return ;
}
单路增广SPFA
于是学习了一下多路增广SPFA的写法，似乎就是用SPFA跑出一些可行路线，然后 dinic，据说在边多流量少的图上作用很好；
竟然一下子跑得飞快，吓了一跳！这时间根本不是一个层次的啊！实在是妙！
代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int const xn=1e5,xm=4e5,inf=1e9;
int n,m,hd[xn],ct=,to[xm],nxt[xm],w[xn],c[xn];
int dis[xn],pre[xn],S,T,cur[xn],ans;
bool vis[xn];
queue<int>q;
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
int Min(int x,int y){return x<y?x:y;}
void ade(int x,int y,int z,int f){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; w[ct]=z; c[ct]=f;}
void add(int x,int y,int z,int f){ade(x,y,z,f); ade(y,x,-z,);}
int d[],bin[];
int id(int x,int y,int k){return ((x-)*m+y-)*+k;}
inline int get(int x)
{
int ret=;
for(int i=;i<=;i++)
if(x&bin[i-])d[i]=,ret++; else d[i]=;
return ret;
}
inline int op(int x){if(x<=)return x+; return x-;}
inline bool ck(){return (d[]&&d[]&&!d[]&&!d[])||(d[]&&d[]&&!d[]&&!d[]);}
bool SPFA()
{
for(int i=S;i<=T;i++)vis[i]=;
for(int i=S;i<=T;i++)dis[i]=inf;
dis[S]=, q.push(S);
while(q.size())
{
int x=q.front(); q.pop(), vis[x]=;
for(int i=hd[x],u;i;i=nxt[i])
if(dis[u=to[i]]>dis[x]+w[i]&&c[i])
{
dis[u]=dis[x]+w[i];
if(!vis[u])vis[u]=,q.push(u);
}
}
return dis[T]!=inf;
}
int dfs(int x,int fl)
{
if(x==T)return fl;
vis[x]=;
for(int &i=cur[x],u,tmp;i;i=nxt[i])
if(!vis[u=to[i]]&&c[i]&&dis[u]==dis[x]+w[i])
if(tmp=dfs(u,Min(fl,c[i])))
{c[i]-=tmp,c[i^]+=tmp,ans+=w[i]*tmp; return tmp;}
return ;
}
int MCMF()
{
int ret=;
while(SPFA())
{
for(int i=S;i<=T;i++)cur[i]=hd[i];
int tmp;
while(tmp=dfs(S,inf))ret+=tmp;
}
return ret;
}
int main()
{
n=rd(); m=rd(); S=; T=n*m*+;
bin[]=; for(int i=;i<=;i++)bin[i]=(bin[i-]<<);
int goal=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
int x=rd(); int cnt=get(x); goal+=cnt;
bool t=(((i+j)&)==);
if(t){for(int k=;k<=;k++)if(d[k])add(S,id(i,j,k),,);}
else {for(int k=;k<=;k++)if(d[k])add(id(i,j,k),T,,);}
if(x==||x==)continue;
if(cnt==)
{
int nw; for(int k=;k<=;k++)if(d[k]){nw=k; break;}
if(t){for(int k=;k<=;k++)if(!d[k])add(id(i,j,nw),id(i,j,k),(k==op(nw)?:),);}//id(i,j,nw)!!
else {for(int k=;k<=;k++)if(!d[k])add(id(i,j,k),id(i,j,nw),(k==op(nw)?:),);}
}
if(cnt==)
{
int nw; for(int k=;k<=;k++)if(!d[k]){nw=k; break;}
if(t){for(int k=;k<=;k++)if(d[k])add(id(i,j,k),id(i,j,nw),(k==op(nw)?:),);}
else {for(int k=;k<=;k++)if(d[k])add(id(i,j,nw),id(i,j,k),(k==op(nw)?:),);}
}
if(cnt==)
{
if(t){for(int k=;k<=;k++)if(d[k])add(id(i,j,k),id(i,j,op(k)),,);}
else {for(int k=;k<=;k++)if(d[k])add(id(i,j,op(k)),id(i,j,k),,);}
}
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(((i+j)&)==)
{
if(i>)add(id(i,j,),id(i-,j,),,);
if(j<m)add(id(i,j,),id(i,j+,),,);
if(i<n)add(id(i,j,),id(i+,j,),,);
if(j>)add(id(i,j,),id(i,j-,),,);
}
if(goal&){puts("-1"); return ;} goal>>=;
int flow=MCMF();
if(flow==goal)printf("%d\n",ans);
else puts("-1");
return ;
}