方案合法相当于要求接口之间配对，黑白染色一波，考虑网络流。有一个很奇怪的限制是不能旋转直线型水管，考虑非直线型水管有什么特殊性，可以发现其接口都是连续的。那么对于旋转水管，可以看做是把顺/逆时针方向上最后的接口提到最前。于是用四个点表示某格子的四个方向，以上述方式只移动一次就能相互转换的方向之间连费用1的边。然后在相邻格子可以相互匹配的方向之间连边，跑费用流即可。注意费用流的无向边必须按有向边的方式建反向边。不明白讨论一大串的是在干啥。

　　

　　然后就非常悲惨了。多路增广的费用流会跑的很快，然而并不会。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 10010#define K 2010#define S 10001#define T 10002char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,m,id[K][4],p[N],d[N],q[N],pre[N],t=-1,cnt,tot,ans,val;bool flag[N];struct data{ int to,nxt,cap,flow,cost;}edge[N<<6];void addedge(int x,int y,int z,int cost){ t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].cap=z,edge[t].flow=0,edge[t].cost=cost,p[x]=t; t++;edge[t].to=x,edge[t].nxt=p[y],edge[t].cap=0,edge[t].flow=0,edge[t].cost=-cost,p[y]=t;}inline int trans(int x,int y){ return (x-1)*m+y;}inline bool isblack(int x,int y){ return (x&1)^(y&1);}inline int inc(int &x){x++;if (x>cnt+3) x-=cnt+3;return x;}bool spfa(){ memset(d,42,sizeof(d));d[S]=0; memset(flag,0,sizeof(flag)); int head=0,tail=1;q[1]=S; do { int x=q[inc(head)];flag[x]=0; for (int i=p[x];~i;i=edge[i].nxt) if (d[x]+edge[i].cost
           
            
             >=1; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (isblack(i,j)) { int v=trans(i,j); if (i>1) addedge(id[v][0],id[trans(i-1,j)][2],1,0); if (j
             
              1) addedge(id[v][3],id[trans(i,j-1)][1],1,0); } ekspfa(); if (ans