解題：2017清華集訓 無限之環

題面

費用流

把每種水管再拆出來四個方向的接頭，然后根據水管的形狀連出旋轉時的代價。最后黑白染色成二分圖，然后白點對應的接頭向黑點對應的接頭連邊，源點向白點自己連邊，黑點自己向匯點連邊。

怎么連邊？我是大力討論16種情況連的，應該是可以巧妙一點的=。=

洛谷不開O2會T，LOJ過了

// luogu-judger-enable-o2
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int B=2005,N=10005,M=120005,inf=1e9;
const int mov[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int n,m,s,t,t1,t2,t3,t4,id,cnt,tot,sum,maxf,minc;
int noww[2*M],goal[2*M],flow[2*M],cost[2*M];
int p[N],mflw[N],mcst[N],queu[N],pren[N],pree[N];
int mapp[B][B],idx[B][B],hed[B][B],tmp[5],hmap[5];
queue<int> qs;
void link(int f,int t,int v,int c,int x)
{
    if(x) swap(f,t);
    noww[++cnt]=p[f],p[f]=cnt;
    goal[cnt]=t,flow[cnt]=v,cost[cnt]=c;
    noww[++cnt]=p[t],p[t]=cnt;
    goal[cnt]=f,flow[cnt]=0,cost[cnt]=-c;
}
int Bitcount(int x)
{
    int ret=0;
    while(x)
        ret++,x-=x&-x;
    return ret; 
}
void Create(int x,int y,int z)
{
    int typ=mapp[x][y],nde=idx[x][y];
    for(int i=1;i<=4;i++) tmp[i]=++tot;
    hed[x][y]=Bitcount(typ);
    if(!typ) 
        for(int i=1;i<=4;i++)
            link(nde,tmp[i],0,inf,z);
    else if(typ==1)
    {
        link(nde,tmp[1],1,0,z);
        link(tmp[1],tmp[2],1,1,z);
        link(tmp[1],tmp[3],1,2,z);
        link(tmp[1],tmp[4],1,1,z);
    } 
    else if(typ==2)
    {
        link(tmp[2],tmp[1],1,1,z);
        link(nde,tmp[2],1,0,z);
        link(tmp[2],tmp[3],1,1,z);
        link(tmp[2],tmp[4],1,2,z);
    } 
    else if(typ==3)
    {
        link(nde,tmp[1],1,0,z);
        link(nde,tmp[2],1,0,z);
        link(tmp[1],tmp[3],1,1,z);
        link(tmp[2],tmp[4],1,1,z);
    }
    else if(typ==4)
    {
        link(tmp[3],tmp[1],1,2,z);
        link(tmp[3],tmp[2],1,1,z);
        link(nde,tmp[3],1,0,z);
        link(tmp[3],tmp[4],1,1,z);
    }
    else if(typ==5)
        for(int i=1;i<=4;i++)
            link(nde,tmp[i],(i%2)?1:0,(i%2)?0:inf,z);
    else if(typ==6)
    {
        link(nde,tmp[2],1,0,z);
        link(nde,tmp[3],1,0,z);
        link(tmp[2],tmp[4],1,1,z);
        link(tmp[3],tmp[1],1,1,z);
    }
    else if(typ==7)
    {
        link(nde,tmp[1],1,0,z);
        link(nde,tmp[2],1,0,z);
        link(nde,tmp[3],1,0,z);
        link(tmp[1],tmp[4],1,1,z);
        link(tmp[2],tmp[4],1,2,z);
        link(tmp[3],tmp[4],1,1,z);
    }
    else if(typ==8)
    {
        link(tmp[4],tmp[1],1,1,z);
        link(tmp[4],tmp[2],1,2,z);
        link(tmp[4],tmp[3],1,1,z);
        link(nde,tmp[4],1,0,z);
    }
    else if(typ==9)
    {
        link(nde,tmp[1],1,0,z);
        link(nde,tmp[4],1,0,z);
        link(tmp[1],tmp[3],1,1,z);
        link(tmp[4],tmp[2],1,1,z);
    }
    else if(typ==10)
        for(int i=1;i<=4;i++)
            link(nde,tmp[i],(i%2)?0:1,(i%2)?inf:0,z);
    else if(typ==11)
    {
        link(nde,tmp[1],1,0,z);
        link(nde,tmp[2],1,0,z);
        link(nde,tmp[4],1,0,z);
        link(tmp[1],tmp[3],1,2,z);
        link(tmp[2],tmp[3],1,1,z);
        link(tmp[4],tmp[3],1,1,z);
    }
    else if(typ==12)
    {
        link(nde,tmp[3],1,0,z);
        link(nde,tmp[4],1,0,z);
        link(tmp[3],tmp[1],1,1,z);
        link(tmp[4],tmp[2],1,1,z);
    }
    else if(typ==13)
    {
        link(nde,tmp[1],1,0,z);
        link(nde,tmp[3],1,0,z);
        link(nde,tmp[4],1,0,z);
        link(tmp[1],tmp[2],1,1,z);
        link(tmp[3],tmp[2],1,1,z);
        link(tmp[4],tmp[2],1,2,z);
    }
    else if(typ==14)
    {
        link(nde,tmp[2],1,0,z);
        link(nde,tmp[3],1,0,z);
        link(nde,tmp[4],1,0,z);
        link(tmp[2],tmp[1],1,1,z);
        link(tmp[3],tmp[1],1,2,z);
        link(tmp[4],tmp[1],1,1,z);
    }
    else if(typ==15)
        for(int i=1;i<=4;i++)
            link(nde,tmp[i],1,0,z);
}
void Init(int st,int ed)
{
    memset(mflw,0x3f,sizeof mflw);
    memset(mcst,0x3f,sizeof mcst);
    memset(queu,0,sizeof queu),pren[ed]=-1;
    qs.push(st),queu[st]=true,mcst[st]=0;
}
bool SP(int st,int ed)
{
    Init(st,ed); 
    while(!qs.empty())
    {
        int tn=qs.front();
        qs.pop(); queu[tn]=false;
        for(int i=p[tn],g;i;i=noww[i])
            if(mcst[g=goal[i]]>mcst[tn]+cost[i]&&flow[i])
            {
                pren[g]=tn,pree[g]=i;
                mcst[g]=mcst[tn]+cost[i];
                mflw[g]=min(mflw[tn],flow[i]);
                if(!queu[g]) qs.push(g),queu[g]=true;
            }
    }
    return ~pren[ed];
}
void MCMF(int st,int ed)
{
    while(SP(st,ed))
    {
        maxf+=mflw[ed],id=ed;
        minc+=mflw[ed]*mcst[ed]; 
        while(id!=st)
        {
            flow[pree[id]]-=mflw[ed];
            flow[pree[id]^1]+=mflw[ed];
            id=pren[id];
        }
    }
}
int main ()
{
    scanf("%d%d",&n,&m),cnt=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&mapp[i][j]);
            idx[i][j]=++tot,Create(i,j,(i+j)%2);
        }
    s=++tot,t=++tot;
    hmap[0]=3,hmap[1]=4,hmap[2]=1,hmap[3]=2;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if((i+j)%2==0) 
            {
                link(s,idx[i][j],inf,0,0),sum+=hed[i][j];
                for(int k=0;k<4;k++)
                {
                    int tx=i+mov[k][0],ty=j+mov[k][1];
                    if(tx>=1&&tx<=n&&ty>=1&&ty<=m)
                        link(idx[i][j]+k+1,idx[tx][ty]+hmap[k],1,0,0);
                }
            }
            else 
                link(idx[i][j],t,inf,0,0);
        }
    MCMF(s,t);
    if(maxf!=sum) printf("-1");
    else printf("%d",minc);
    return 0;
}

?