首页 > 其他分享 >缩点-DAG 性质的应用:P2002,P1262,P2341,P1407,P2746(P2812)

缩点-DAG 性质的应用:P2002,P1262,P2341,P1407,P2746(P2812)

时间:2023-02-04 11:58:04浏览次数:75  
标签:缩点 P2002 连通 DAG 出度 入度 scc 分量

缩点不只用于转化图为 DAG,还可以进一步发掘图的性质,从而将题目变成结论题所求信息转化到图上,方便建模。

P2002

https://www.luogu.com.cn/problem/P2002

在一个强连通分量里面的城市是绝对可以互相到达的,所以我们缩点。然后在新图中,我们只需要给入度为 \(0\) 的点发送信息,整张图都可以走完了。但其实我们并不需要建新图,只需要知道图中新点的入度,也就是找到新图中需要建哪些边。如果原图中一条边连接的两个端点在同一个强连通分量里面,那么这条边就不是新图里的边,防止窝里斗;反之,如果 \(scc_u \ne scc_v\),则 \(u \rightarrow v\)是新图里的边,这时候 \(in_{scc_v}\) 自加。最后统计 \(in_u=0\) 的点数。

P1262

https://www.luogu.com.cn/problem/P1262

把间谍 \(u\) 可以揭发 \(v\) 当作连边 \(u \rightarrow v\),这样可以发现,在一个强连通分量内,只要有一个间谍被收买,其他的间谍都寄了。所以我们缩点,点权取强连通分量内最低的收买费用,所有点权加起来就可以了。那么什么时候无解呢?当有一个强连通分量的点权为 \(inf\) 也就是说这个强连通分量里面的间谍都不可以被金钱收买,这时候我们输出这个强连通分量里面编号最小的间谍即可。

P2341

https://www.luogu.com.cn/problem/P2341

受欢迎的奶牛是被所有牛喜爱,如果我们将 \(u\) 喜欢 \(v\) 转化为 \(u \rightarrow v\) 有一条有向边,那么受欢迎的牛就是所有其他的奶牛都可以到达的牛。缩点后,每个强连通分量记录其大小 \(siz\),如果新图内只有一个出度为 \(0\) 的点,那么所有其他点内奶牛都可以到达这个出度为 \(0\) 的点,这个强连通分量里面的牛都是受欢迎的奶牛。但是如果缩完后有多个出度为 \(0\) 的点,那么这些出度为 \(0\) 的点都不可以互相到达,所以就没有受欢迎的牛了。

P1407

https://www.luogu.com.cn/problem/P1407

男女结婚关系,然后题目中说男男女女不可以结婚(完全错误的,彻底错误的,毫不讲理的,固执己见的,墨守成规的,老套过时的),所以这很像一个二分图匹配问题。\(u\) 和 \(v\) 现在是夫妻,连边 \(u \rightarrow v\),题目中相当于给了我们一个完美匹配,如果我们拆散 \(u\) 和 \(v\),其他的不变,如果可以从 \(u\) 出发再找到一条增广路,就说明这对夫妻关系是不稳定的,反之亦然。

当然,对于缩点的做法,我们可以一样地建边,在一个强连通分量里面的夫妻是不稳定的,反之亦然,所以缩点后判断 \(scc_u\) 和 \(scc_v\) 就可以了。

P2746(P2812)

严谨的结论题。子任务 A 相当于 P2002,缩点后统计入度为 \(0\) 的点数即可。

子任务 B 就是问我们把新图变为一个环需要添加的最少边数。https://www.luogu.com.cn/blog/Ametsuji-tachiaki/solution-p2746 这篇文章对我启发很大,分类讨论:如果一个点有入度也有出度,那是怎么放都可以到达的;那如果没有入度或出度,我们将这些点首尾相连,合成二星卡,技能翻倍,由无出度点连向无入度点,当然每一个无入度或出度点都要被连,这样新图就是一个环了。所以答案为入度为 \(0\) 的点数和出度为 \(0\) 的点数的最大值。

标签:缩点,P2002,连通,DAG,出度,入度,scc,分量
From: https://www.cnblogs.com/Ziqqurat/p/17091206.html

相关文章

  • 缩点-将图转化为 DAG 跑 DP :P1455,P2169
    之前有提到,缩点可以将一张有向图转化为一张有向无环图(DAG),这样我们就可以在图上跑DP了。而我们实现DP的手段一般是在拓扑排序中实现,有时候也会用到最短路。P1455https......
  • 缩点学习笔记
    假如题目名称不是“【模板】缩点”的话,是否能想到缩点?这道题如何联想到缩点?首先题目给出的图,可能存在强连通分量,这样的强连通分量中,所有的点权都可全部取到,所以如果走到......
  • 缩点 P2812 校园网络【[USACO]Network of Schools加强版】
    首先找出图中的强连通分量,用tarjan算法。强连通分量内部强联通,所以将其看成一个点是不影响的。进行缩点之后,整张图变成了一个有向无环图。首先对于每一条边进行检测,如果......
  • 「解题报告」ARC136E Non-coprime DAG
    很妙啊这题。我们来分析\(x\)能到\(y\)的数有什么性质。既然是不互质,那么可以考虑看这个数的最小质因子是什么。记\(f(x)\)为\(x\)的最小质因子。我们将质因子......
  • 经典问题 1 —— DAG 上区间限制拓扑序
    问题描述给定一个DAG,求一个拓扑序,使得节点\(i\)的拓扑序\(\in[l_i,r_i]\)。题解首先进行一个预处理:对于所有\(u\),令\(\forall(v,u)\inE,l_u\leftarrow\max(l......
  • 洛谷 P1002 [NOIP2002 普及组] 过河卒
    P1002[NOIP2002普及组]过河卒#include<stdio.h>#include<stdlib.h>#include<string.h>intmain(){intHorse_y[8]={2,1,-1,-2,-2,-1,1,2};......
  • SDUT DAG优化
    SDUTDAG优化题目描述大家都学过了代码优化,其中有一个DAG优化,这次我们就练习这个操作。输入输入第一行为一个整数n(n<100),表示该组输入的表达式的个数之后n行为表达式......
  • P1073 [NOIP2009 提高组] 最优贸易 强联通分量+缩点
    //题意:给出有向图,有环(SCC),每个节点有一个商品值,小明想从1点走向n点,同时想要进行一次贸易,即从路线上某个点买入商品,又在某个节点卖出,询问最大收益是多少(如果收益为负数......
  • Dagger2依赖注入框架
    Dagger2简介:Dagger:“AfastdependencyinjectorforAndroidandJava“,其最大的好处就是莫跨界见解耦,这个耦合是由类之间的以来引起的,依赖注入的配置独立于初始化出,配......
  • 火山引擎DataLeap数据调度实例的 DAG 优化方案
    更多技术交流、求职机会,欢迎关注字节跳动数据平台微信公众号,并进入官方交流群实例DAG介绍DataLeap是火山引擎自研的一站式大数据中台解决方案,集数据集成、开发、运......