【2018SCUACM FurtherTraining 22 差分约束+LCA】

题目来源

A:UVA11478

B:POJ1741

C:POJ3417

D:HDU2586

解题报告

A:差分约束+SPFA。

首先,不难看出,对一个点,把作用于其上的\(d\)分开操作和求出所有的\(d\)之和\(S(d)\)再一并操作效果是一样的。换句话说,设\(S(a)\)为作用于\(a\)上的\(d\)之和,则进入\(a\)的边,边权都需要减少\(S(a)\);从\(a\)出去的边,边权都需要增加\(S(a)\)。再来看,假设\(a,b\)之间的某条边边权为\(w(a,b)\),则经过操作后其边权变为\(w(a,b)+S(a)-S(b)\)。

题目要求最小边最大且大于等于1,不难想到二分答案,我们二分答案\(x\)表示所有边都能大于等于\(x\),等价于\(w(a,b)+S(a)-S(b)\ge x\),移项可得\(S(b)-S(a)\le w(a,b)-x\),于是就变成了可否满足\(E\)个这样的不等式,很明显就是一个差分约束问题了。

上边我们说过,合并做和分开做是一样的,所以我们不妨设\(a,b\)间的初始边权\(w(a,b)=d\),多次操作相当于在\(a,b\)间加很多条这样的边。根据\(S(b)-S(a)\le w(a,b)-x\)以及差分约束系统的解法,对每个\(x\),将\(w(a,b)\)变为\(w(a,b)-x\),然后判断有没有负环就是了,如果有,就是无解,否则有解。

再来说说\(Infinite\)与\(No\ Solution\)的情况,由于答案不可能大于最大边,所以首先对最大边+1跑一遍\(SPFA\) ,这都可以满足那肯定是\(Infinite\)了;反之,如果连最小的\(1\)都不能满足,那就是\(No\ Solution\)。

至于网上说的超级源点跟所有点相连,究其本质,是因为一个差分约束系统给出的图可能不是一个连通图,此种情况下不连通表示某一对或多对点之间并无约束关系,最小值无穷大,自然是大于等于\(x\)的,所以是有解并且解无穷大的状态。因此,我们使用\(SPFA\)判断负环的时候,要先将每个点都入队。

B:点分治模板题,点分治的思路大概就是不断找重心,路径可分为两种,一种是经过这个点的,另一种是不经过这个点的。对于不经过这个点的情况,只需要按照这个点继续分治划分成更小的子树,迟早会转化成第一种情况。

具体的思路这篇文章讲的挺好:https://www.cnblogs.com/ECJTUACM-873284962/p/6618855.html

C:树形DP+LCA。考虑原来的边与新增的边的关系:新增边必然与原树中的某些边形成一个环。

仔细分析可以发现,若我们能够记录边属于几个环,就可以得出答案:

①若该边不属于任何环,则这条边就是桥,删去后图直接不连通,因此,此种情况下答案增加\(m\)

②若该边仅属于一个环,那么删去这条边,以及导致它成为环中边的那条新边后图不连通,仅有这一种删法可让图不连通,因此,此种情况下答案增加\(1\)

③若该边属于两个及以上的环,那么删了这条边,图仍然是连通的,此种情况下答案不增加。

于是乎问题就转化成了如何求每条边属于几个环了,设\(dp[u]\)表示节点\(u\)与其父亲相连的那条边被覆盖的次数(以1为根),每次读入一条新边\((u,v)\),我们令\(dp[u]++,dp[v]++,dp[LCA(u,v)]-2\),为什么这样做呢?类似于\(u\)到\(v\)的路径求法,我们自根向下进行遍历,回溯时累加子节点的\(dp\)值,按上面操作后可以发现根到\(LCA\)的部分被抵消掉了,于是每个点的累加和就是其与父节点边被环包含的次数,然后分情况计算即可。

PS:本题数据大,需要用\(long\ long\)

 

D:\(LCA\)模板题,没啥好说的,求出两点\(a,b\)到树根的距离和\(LCA(a,b)\)到树根的距离,答案就是\(dis[a]+dis[b]-2*dis[LCA(a,b)]\)。

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*