洛谷题材传送门。洛谷问题传送门。

说明

输入格式:

首先实施两只正整数 n, m,代表网格的分寸。
连接下去 n 行每行 m 个数,每个数是 [0,15] 中之一个,你得将该当做一个 4
位的次上制数,从低及强每一样各类分别表示初始局面中这个格子上、右、下、左方向上是否生水管接头。
专门地,如果是累是 0 ,则象征是职位并未水管。
依照 3(0011(2)) 代表及及右手出懂得,也就算是一个 L 型;
要 12(1100(2)) 代表下和谬误来理解,也就是是用 L 型旋转 180 度。

出口样例#2:

-1

题目

输出格式:

输出共一行,表示最少操作次数。如果无法达成目标,输出-1.

输入样例#1:

2 3
3 14 12
3 11 12

题目

出口样例#2:

-1

【样例 1 解释】

样例 1 棋盘如下
转方式很强烈,先将左上角虚线方格内之水管顺时针转 90 度

然后右下比赛虚线方格内的水管逆时针旋转 90 度,这样就使得水管封闭了

思路分析

意味着这是相同道思维神题。。。。。。
有人第一眼看上去觉得这要跑费用流吗?
然而如果会建图,剩下的饶是学模板的从了。

咱们这么来解。对于每个方格上之水管的各级一个支管,有且仅发生一个另方格上的支管与那个不断,这样即使非会见漏水了。用网络流知识表述,就是每个支管容量只能为1,且都要满流,于是跑顶小费用可行流

然就是出了太了不起情况,整个管网也不必然是一整个联通块,而恐怕为分成多块。因此,怎样强制使每半独相邻之方格上且有流量也?就设拿来自汇点连到每个格子上。而且,还要对每个格点染色,相邻之星星点点单格点,一个连源点,一个并汇点。具体的落实,就要用格点列坐标和底奇偶性来判断。

使发生的费为?当然是转造成的呀!真正的思索就是体现于这边了。因为旋转还见面招致接触点的别,所以一定是如拆点的,一个方格拆成五个点,上下左右蒙受。。。。。。中间点并上源/汇点,并冲支管情况望四周连容量1,费用0的界限。四周视作接触点,与相应相邻之其它一个点点并容量1,费用0的尽头。讨论相邻两独方格格因旋转而发出的发出费用之连边,实在是无比碍事了。。。。。。猛然发现,所有的景况,其实仅仅需要在其间开展转发就哼了。

享有的方格,我们约分为以下几近似进行座谈。

思路分析

表示即是一律鸣思维神题。。。。。。
有人第一眼看上去觉得这要跑费用流吗?
可是一旦会建图,剩下的即是效仿模板的从事了。

咱们如此来掌握。对于每个方格上之水管的每一个支管,有且仅发生一个任何方格上的支管与那持续,这样就算无会见漏水了。用网络流知识表述,就是每个支管容量只能为1,且全要满流,于是跑极致小费用而行流

然而即使有了太美情况,整个管网也无自然是一整个联通块,而或被分为多片。因此,怎样强制使各国半只相邻的方格上还产生流量也?就假设将自汇点连到每个格子上。而且,还要针对每个格点染色,相邻的简单只格点,一个连源点,一个并汇点。具体的实现,就要动用格点队坐标和底奇偶性来判断。

使生的支出为?当然是转造成的哪!真正的沉思就是体现在此了。因为旋转还会见招致接触点的变型,所以一定是一旦拆点的,一个方格拆成五只点,上下左右着。。。。。。中间点并上源/汇点,并冲支管情况于四周连容量1,费用0的无尽。四周视作接触点,与相应相邻之其它一个点点并容量1,费用0的底限。讨论相邻两单方格格因旋转而来的来费用之连边,实在是绝碍事矣。。。。。。猛然察觉,所有的情事,其实就待以里边进行转向就哼了。

富有的方格,我们大约分为以下几近乎进行讨论。

第一种:射线型

这种好惩治。射线对上面,那么尽管叫左、下、右接触点一直连接达接触点。左,右连上去,表示一旦反90渡过,所以费用为1。下面连上失去费用为2

洛谷问题传送门

第二种:直角型

这种理解起来就来难度了。如果顺时针转90过,会变成这样

相当给原来并上接触点的支管连到了底,那么上与下建平修容量为1,费用为1的限度。同样的理,逆时针转90渡过,左和右打平漫漫容量为1,费用为1的度。再来谈谈反180度过,这时候,会经既有的边由左、下直换到右手、上,费用加起刚刚是2,所以不用连还多边了。

输入样例#1:

2 3
3 14 12
3 11 12

【样例 3 解释】

样例 3
为问题叙述中之次张图,将除核心方格以外的每个方格内之水管都转 180
度即可。

第二种:直角型

这种理解起来便生出难度了。如果顺时针转90过,会成这样

一定给原并上接触点的支管连到了下面,那么上与生建平条容量为1,费用为1的无尽。同样的道理,逆时针转90过,左和右手打同等修容量为1,费用为1的限度。再来讨论反180渡过,这时候,会经已部分边由左、下直接换至右手、上,费用加起来正好是2,所以无用连再次多边了。

输入输出样例

【样例 3 解释】

样例 3
为问题叙述负的次摆放图片,将除核心方格以外的每个方格内之水管都转 180
度即可。

出口格式:

出口共一行,表示最少操作次数。如果无法上目标,输出-1.

第一种:射线型

这种好惩治。射线对上面,那么就是为左、下、右接触点一直连接达接触点。左,右连上去,表示要反90度过,所以费用为1。下面连上失去费用为2

出口样例#3:

16

第三种:T字型

比如说前一样讨论,也可建边。从下往左、右各打同等修容量为1,费用为1的界限,向上建同等长达费用为2的限度。这里就是留读者自己想想啦。


如上三栽情景,每一样种都发4只形状,但连边方法还是相同的。
再有直线型,十字型和空的,要么不可知更改,要么改变了没有意义,就不用内部建边了。

脚贴代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define R register int
#define UP(U) U+turn*sum
#define RI(U) U+((turn+1)&3)*sum
#define DO(U) U+((turn+2)&3)*sum
#define LE(U) U+((turn+3)&3)*sum
#define MD(U) U+(sum<<2)//上面几个用来计算对应点的数组下标,上下左右中。。。
const int INF=2147483647,N=20009,M=200009;
int sum,P=1,S=0,T;//sum方格总数,P建图循环变量,S、T为源汇点
int he[N],ne[M],to[M],f[M],c[M];//f流量,c费用
int q[N],d[N],pre[N];//q队列,d距离,pre记录最短路
bool inq[N];//标记是否在队列中
inline void in(R&z)//快读
{
    register char c=getchar();
    while(c<'-')c=getchar();
    z=c&15;c=getchar();
    while(c>'-')z*=10,z+=c&15,c=getchar();
}
inline void add(R u,R v,R flow,R cost,R tp)//建边,tp表示染色属性
{
    if(tp){tp=u;u=v;v=tp;}//如果是奇数点,所有的边都要反向,要流出去
    to[++P]=v;ne[P]=he[u];he[u]=P;c[P]=cost;f[P]=flow;
    to[++P]=u;ne[P]=he[v];he[v]=P;c[P]=-cost;
}
#define PB(X) q[t]=X;if(++t==N)t=0
#define PF(X) if(--h<0)h=N-1;q[h]=v//手打了一下双向循环队列
inline bool spfa()//模板,加了两种优化
{
    R h=0,t=1,i,u,v,dn,cnt=1,sum=0;
    for(i=S+1;i<=T;++i)d[i]=INF;
    q[0]=S;inq[0]=1;
    while(h!=t)
    {
        u=q[h];
        if(++h==N)h=0;
        if(d[u]*cnt>sum){PB(u);continue;}//LLL优化
        --cnt;sum-=d[u];
        for(i=he[u];i;i=ne[i])
            if(f[i]&&d[v=to[i]]>(dn=d[u]+c[i]))
            {
                if(inq[v])sum-=d[v];
                else
                {
                    inq[v]=1;++cnt;
                    if(d[v]<d[q[h]]){PB(v);}
                    else{PF(v);}//SLF优化
                }
                pre[v]=i;
                sum+=(d[v]=dn);
            }
        inq[u]=0;
    }
    return d[T]!=INF;
}
int main()
{
    R n,m,i,j,k=1,t,shape,turn,totf=0,mf=0,mc=0;//totf总流量,mf最大可行流,mc总费用
    in(n);in(m);
    sum=n*m;T=sum*5+1;
    for(i=0;i<n;++i)
        for(j=0;j<m;++j,++k)
        {
            turn=0;//turn下面会用来翻转,将同类型的水管归类到一起
            t=(i+j)&1;//t是染色属性,只要判断奇偶
            if(t)add(S,MD(k),INF,0,0);
            else add(MD(k),T,INF,0,0);
            if(i)add(DO(k-m),UP(k),1,0,t);
            if(j)add(RI(k-1),LE(k),1,0,t);
            in(shape);
            if(shape&1)add(UP(k),MD(k),1,0,t),++totf;//统计总流量
            if(shape&2)add(RI(k),MD(k),1,0,t),++totf;//因为每个流拆成了两段
            if(shape&4)add(DO(k),MD(k),1,0,t),++totf;//所以最终结果会是实际的两倍
            if(shape&8)add(LE(k),MD(k),1,0,t),++totf;//中点与四周点连边
            switch(shape)
            {
            case 8:++turn;//1000 ←
            case 4:++turn;//0100 ↓
            case 2:++turn;//0010 →
            case 1:       //0001 ↑
                add(RI(k),UP(k),1,1,t);
                add(DO(k),UP(k),1,2,t);
                add(LE(k),UP(k),1,1,t);
                break;//四种形状内部连边情况是一样的,转一下统一处理就方便些了,下面同理
            case 9:++turn; //1001 ┘
            case 12:++turn;//1100 ┐
            case 6:++turn; //0110 ┌
            case 3:        //0011 └
                add(DO(k),UP(k),1,1,t);
                add(LE(k),RI(k),1,1,t);
                break;
            case 13:++turn;//1101 ┤
            case 14:++turn;//1110 ┬
            case 7:++turn; //0111 ├
            case 11:       //1011 ┴
                add(DO(k),LE(k),1,1,t);
                add(DO(k),UP(k),1,2,t);
                add(DO(k),RI(k),1,1,t);
                break;
            }
        }
    while(spfa())
    {
        m=INF;//这里m记下流量
        for(i=T;i!=S;i=to[k^1])
        {
            k=pre[i];
            if(m>f[k])m=f[k];
        }
        mf+=m;
        for(i=T;i!=S;i=to[k^1])
        {
            k=pre[i];
            f[k]-=m;f[k^1]+=m;
            mc+=m*c[k];
        }
    }
    printf("%d",totf==mf<<1?mc:-1);//注意如果没能流满就输-1
    return 0;
}

洛谷问题传送门

出口样例#3:

16

输入输出格式

输入样例#2:

3 2
1 8
5 10
2 4

【样例 1 解释】

样例 1 棋盘如下
盘方式充分显眼,先将左上角虚线方格内的水管顺时针转 90 度

下一场右下比赛虚线方格内的水管逆时针旋转 90 度,这样尽管使水管封闭了

【样例 2 解释】

样例 2 呢题材叙述负的率先摆图纸,无法直达目标。

出口样例#1:

2

输出样例#1:

2

第三种:T字型

例如前一样讨论,也可以建边。从生向左、右各修同等长长的容量为1,费用为1的限度,向上澳门皇冠官网app建平漫漫费用为2的界限。这里虽留下读者自己思考啦。


以上三种情形,每一样栽都生4只样子,但连边方法都是如出一辙的。
再有直线型,十字型和空的,要么不能够转,要么改变了从未有过意义,就甭内部建边了。

下贴代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define R register int
#define UP(U) U+turn*sum
#define RI(U) U+((turn+1)&3)*sum
#define DO(U) U+((turn+2)&3)*sum
#define LE(U) U+((turn+3)&3)*sum
#define MD(U) U+(sum<<2)//上面几个用来计算对应点的数组下标,上下左右中。。。
const int INF=2147483647,N=20009,M=200009;
int sum,P=1,S=0,T;//sum方格总数,P建图循环变量,S、T为源汇点
int he[N],ne[M],to[M],f[M],c[M];//f流量,c费用
int q[N],d[N],pre[N];//q队列,d距离,pre记录最短路
bool inq[N];//标记是否在队列中
inline void in(R&z)//快读
{
    register char c=getchar();
    while(c<'-')c=getchar();
    z=c&15;c=getchar();
    while(c>'-')z*=10,z+=c&15,c=getchar();
}
inline void add(R u,R v,R flow,R cost,R tp)//建边,tp表示染色属性
{
    if(tp){tp=u;u=v;v=tp;}//如果是奇数点,所有的边都要反向,要流出去
    to[++P]=v;ne[P]=he[u];he[u]=P;c[P]=cost;f[P]=flow;
    to[++P]=u;ne[P]=he[v];he[v]=P;c[P]=-cost;
}
#define PB(X) q[t]=X;if(++t==N)t=0
#define PF(X) if(--h<0)h=N-1;q[h]=v//手打了一下双向循环队列
inline bool spfa()//模板,加了两种优化
{
    R h=0,t=1,i,u,v,dn,cnt=1,sum=0;
    for(i=S+1;i<=T;++i)d[i]=INF;
    q[0]=S;inq[0]=1;
    while(h!=t)
    {
        u=q[h];
        if(++h==N)h=0;
        if(d[u]*cnt>sum){PB(u);continue;}//LLL优化
        --cnt;sum-=d[u];
        for(i=he[u];i;i=ne[i])
            if(f[i]&&d[v=to[i]]>(dn=d[u]+c[i]))
            {
                if(inq[v])sum-=d[v];
                else
                {
                    inq[v]=1;++cnt;
                    if(d[v]<d[q[h]]){PB(v);}
                    else{PF(v);}//SLF优化
                }
                pre[v]=i;
                sum+=(d[v]=dn);
            }
        inq[u]=0;
    }
    return d[T]!=INF;
}
int main()
{
    R n,m,i,j,k=1,t,shape,turn,totf=0,mf=0,mc=0;//totf总流量,mf最大可行流,mc总费用
    in(n);in(m);
    sum=n*m;T=sum*5+1;
    for(i=0;i<n;++i)
        for(j=0;j<m;++j,++k)
        {
            turn=0;//turn下面会用来翻转,将同类型的水管归类到一起
            t=(i+j)&1;//t是染色属性,只要判断奇偶
            if(t)add(S,MD(k),INF,0,0);
            else add(MD(k),T,INF,0,0);
            if(i)add(DO(k-m),UP(k),1,0,t);
            if(j)add(RI(k-1),LE(k),1,0,t);
            in(shape);
            if(shape&1)add(UP(k),MD(k),1,0,t),++totf;//统计总流量
            if(shape&2)add(RI(k),MD(k),1,0,t),++totf;//因为每个流拆成了两段
            if(shape&4)add(DO(k),MD(k),1,0,t),++totf;//所以最终结果会是实际的两倍
            if(shape&8)add(LE(k),MD(k),1,0,t),++totf;//中点与四周点连边
            switch(shape)
            {
            case 8:++turn;//1000 ←
            case 4:++turn;//0100 ↓
            case 2:++turn;//0010 →
            case 1:       //0001 ↑
                add(RI(k),UP(k),1,1,t);
                add(DO(k),UP(k),1,2,t);
                add(LE(k),UP(k),1,1,t);
                break;//四种形状内部连边情况是一样的,转一下统一处理就方便些了,下面同理
            case 9:++turn; //1001 ┘
            case 12:++turn;//1100 ┐
            case 6:++turn; //0110 ┌
            case 3:        //0011 └
                add(DO(k),UP(k),1,1,t);
                add(LE(k),RI(k),1,1,t);
                break;
            case 13:++turn;//1101 ┤
            case 14:++turn;//1110 ┬
            case 7:++turn; //0111 ├
            case 11:       //1011 ┴
                add(DO(k),LE(k),1,1,t);
                add(DO(k),UP(k),1,2,t);
                add(DO(k),RI(k),1,1,t);
                break;
            }
        }
    while(spfa())
    {
        m=INF;//这里m记下流量
        for(i=T;i!=S;i=to[k^1])
        {
            k=pre[i];
            if(m>f[k])m=f[k];
        }
        mf+=m;
        for(i=T;i!=S;i=to[k^1])
        {
            k=pre[i];
            f[k]-=m;f[k^1]+=m;
            mc+=m*c[k];
        }
    }
    printf("%d",totf==mf<<1?mc:-1);//注意如果没能流满就输-1
    return 0;
}

输入输出样例

输入样例#2:

3 2
1 8
5 10
2 4

输入样例#3:

3 3
9 11 3
13 15 7
12 14 6

说明

输入输出格式

【样例 2 解释】

样例 2 吧题材叙述着之首先摆图片,无法直达目标。

输入格式:

率先执两独刚刚整数 n, m,代表网格的大小。
连下 n 行每行 m 个数,每个数是 [0,15] 中的一个,你得以那个作为一个 4
位的亚前行制数,从没有到高每一样员分别代表初始局面中是格子上、右、下、左方向上是否有水管接头。
专门地,如果这个累是 0 ,则意味是职务并未水管。
按部就班 3(0011(2)) 代表及与右边出了解,也就是是一个 L 型;
假若 12(1100(2)) 代表下与错误发了解,也尽管是将 L 型旋转 180 度。

题材叙述

已经发生同等慢性流行的游艺,叫做 Infinity Loop,先来概括的牵线一下斯玩:
玩于一个 n ∗ m
的网格状棋盘上开展,其中有些小方格中会有水管,水管可能以格子某些方向的境界的面临点来接口,所有水管的粗细都同一,所以若简单个相邻方格的协同边界的中段都发生理解,那么可以作为这半只懂得互相连接。水管有因为下
15 种形状:

游玩开始经常,棋盘中水管可能有漏水的地方。
形式化地:如果是有接头,没有同其它接头相连接,那么它们就是一个渗出的地方。
玩家可进行相同种植操作:选定一个包含非直线型水管的方格,将里面的水管绕方格中心顺时针或逆时针旋转
90 度。
直线型水管是恃左图里中路一行的点滴种水管。
临时被起一个初始局面,请问最少进行粗坏操作可以假设棋盘上无在漏水的地方。

题材叙述

已经发生同慢性流行的游艺,叫做 Infinity Loop,先来大概的牵线一下者玩:
打闹于一个 n ∗ m
的网格状棋盘上进展,其中有些小方格中会发出水管,水管可能以格子某些方向的界线的中点来接口,所有水管之粗细都如出一辙,所以要是个别独相邻方格的并边界的中间都发出懂得,那么好看成这有限单亮互相连接。水管有坐下
15 种形状:

玩耍开始经常,棋盘中水管可能存在漏水的地方。
形式化地:如果在有接头,没有跟任何接头相连接,那么她便是一个渗出的地方。
玩家可展开相同种操作:选定一个带有非直线型水管的方格,将其中的水管绕方格中心顺时针或逆时针旋转
90 度。
直线型水管是乘左图里中一行的星星栽水管。
即吃来一个方始局面,请问最少进行多少次操作可以使棋盘上不设有漏水的地方。

输入样例#3:

3 3
9 11 3
13 15 7
12 14 6

相关文章