[BZOJ4086/Luogu3323][SDOI2015]旅行计划(分类讨论,容斥原理,计数)

发布于 2018-05-27  357 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4086/Luogu3323][SDOI2015]旅行计划(分类讨论,容斥原理,计数)

Description

在有 N 座城市的国度.Alice希望可以开始一场充满传奇的旅行。TA 希可以从一个城市出发开始旅行,每次前往一个相邻的城市,途中不重复得经过恰好 K 座城市,最后抵达另外一个城市并结束旅行。需要注意的是,起点与终点也被考虑为经过的城市,也就是说包括起点和终点在内经过的所有城市都是不能重复的。现在,Alice 希望知道哪些城市对 <u,v> 可以作为合法的旅行起点与终点。

Tag

分类讨论,容斥原理,计数

解决思路

看到\(K\)这么小,第一个想到的就是状态压缩。
可惜这道题与状态压缩并没有什么关系。看到数据这么小,于是我们可以数据分治分类讨论一下。
\(K==2\),直接就是每一条边
\(K==3\),对于合法的\(x-u-y\),我们可以枚举\(x,y\),然后扫描从\(x\)出发的每一条边,\(x->t\),看\(t\)是否与\(y\)直接右边相连。
\(K==4\),对于合法的\(x-u-v-y\),同样是枚举\(x,y\),然后分别扫描从\(x\)出发的边\(x->u\)和\(y\)出发的边\(y->v\),看\(u\)与\(v\)是否直接连通。
\(K==5\),从\(K==5\)开始,情况变得有些复杂。对于合法的路径\(x-p-u-q-y\),我们在最外层枚举\(p\)和\(q\),然后扫描\(p\)的出边看\(p->u\)能不能与\(q\)直接相连,这样我们就处理出若干\(p,u,q\)的三元组。然后我们再扫描\(p\)的出边和\(q\)的出边构造出\(x,y\)?
且住,这里我们无法保证\(x,y\)不是我们之前枚举的\(u\)啊。所以利用容斥原理,我们记对于当前的\(p,q\),\(Cnt[i]\)表示\(i\)这个点作为中间点\(u\)几次,\(sum\)记录这一次的\(Cnt[]\)之和,那么我们在枚举\(x,y\)的时候,只需要判断\(sum-Cnt[x]-Cnt[y]\)是不是大于\(0\)就可以知道是否合法了。
代码表示就是这样

\(K==6\),类似\(K==5\)的做法,还是利用容斥。设合法路径为\(x-p-u-v-q-y\),先枚举\(p,q\)并扫描其出边得到\(u,v\),这样就得到了合法的四元组。记\(Cnt[i]\)表示点\(i\)出现在四元组中的次数,\(sum\)记总次数,然后再枚举\(p,q\)的出边得到\(x,y\)。需要注意的是,像上面那样\(Sum-Cnt[x]-Cnt[y]\)是不行的,因为可能\(x-y\)也正好是一对二元组,所以要加上\(x-y\)是否连通,即要判断的应该是\(sum-Cnt[x]-Cnt[y]+Map[x][y]\)是否大于\(0\)
代码是这样的

\(K==7\),点数越来越多了。这一次直接枚举复杂度会太高。设合法路径的形态为\(x-p-u-z-v-q-y\)。我们先预处理处所有的三元组\(u-z-v\),记为\(Node[u][v]\)的元素,然后同样还是枚举\(p,q\),再枚举其出边找到\(u,v\),由于我们已经预处理好了所有的三元组,所以我们可以直接得到\(z=Node[u][v]\),然后依然\(sum\)记录三元组数量,\(Cnt[i]\)记录\(i\)出现的次数。但这还要记录两个值,因为若像上面那样减的话,会多减去\(x,y\)作为三元组两端和分别作为三元组一端与中间的情况,所以记\(Cnt1[i][j]\)表示\(i,j\)分别作为三元组两端的次数,记\(Cnt2[i][j]\)表示\(i\)作为三元组一端,\(j\)作为三元组中间的次数。然后依然枚举\(p,q\)的出边得到\(x,y\),若\(sum-Cnt[x]-Cnt[y]+Cnt1[x][y]+Cnt2[x][y]+Cnt2[y][2]\)大于等于\(0\),则合法。
代码长这样

可以说非常休闲了

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4086/Luogu3323][SDOI2015]旅行计划(分类讨论,容斥原理,计数)


HNCJ OIer