【codeforces】图论杂题

2016年11月6日3722
一些图论简单题:
500A.New Year Transportation
437C.The Child and Toy
510C.Fox And Names
475B.Strongly Connected City
639B.Bear and Forgotten Tree 3
623A.Graph and String
449B.Jzzhu and Cities
543B.Destroying Roads
500A.New Year Transportation
有n个城市排成1排,从第i个城市可以走到\(i+a_i\)号城市,并给定一个城市t,问是否能从1到t?
\(1\leq n,a_i\leq 10^5\)
题解
将1打个标记,从左往右扫一遍,若i打上标记,则将\(i+a_i\)打标记
最后看t是否有标记。

437C.The Child and Toy

n个带权点,m条边的无向图,删除一个点的代价是与这个点相邻的,且没有被删除的点权和。

求将所有点删除的最小代价。

题解

按照从大到小的次序删点。

发现每条边的贡献是连接的两个点的权值的最小值。

\(1\leq n\leq1000,1\leq m\leq 2000\)

510C.Fox And Names

给定n个字符串,问能否存在这样的字母表,使得字符串的排序满足字典序。

\(1\leq n,|S|\leq 100\)

题解

建图后拓扑排序

475B.Strongly Connected City

给定n条水平和m条竖直的单向街道,其互相交叉为n*m个结点,问这些结点是否都能互相到达。

\(1\leq n,m\leq 20\)

题解

1.从每个结点开始dfs,最后看每个结点是否最终被搜到n*m次。

2.求强连通图可以直接套用tarjan算法。

3.实际上只需要判断外环路是否成环即可。

639B.Bear and Forgotten Tree 3

构造一棵n个点,深度h,最长链为d的树。

\(1\leq n,h,d\leq 10^5\)

题解

首先构造一个长度为d的链,然后把其中一个距离边上为h的点变为根。

把剩下的点全都接在根上。

623A.Graph and String

n个结点的无向图,每个结点标号”abc”三个字母其中一个。

将标号为相同字母的结点连边,将所有标号为b的结点与其它标号的结点连边。

给出图的m个连边,求一种合法的标号方案,不存在输出’NO’。

\(1\leq n\leq 500,1\leq m\leq n(n-1)/2\)

题解

如果有一个点和其它点都有连边,将其标号b。

然后选择一个未被标号的点,标号为a,二分图染色。

最后验证一下即可。

449B.Jzzhu and Cities

n个点,m条带权边的无向图,另外还有k条特殊边,每条边连接1和i。

求可以删除这k条边中的多少条,使得每个点到1的最短距离不变。

\(1\leq n,m,K\leq 10^5\)

题解

求1到所有结点的最短路,对于每条特殊边1到x:

若其长度大于dis(x),删除。

否则考察所有非特殊边x-y,若dis(y)+w=dis(x),删除。

否则需要保存一条长度为dis(x)的边。

543B.Destroying Roads

n个结点,m条边的无向图(边权全为1),问最多能删掉多少条边使得s1到t1距离不超过l1,s2到t2距离不超过l2。

\(1\leq n\leq 500,1\leq m\leq n(n-1)/2\)

题解

其实就是问,至少需要多少条边,才能使得s1到t1距离不超过l1,s2到t2距离不超过l2。

如果这两条路径不相交,那么答案为dis(s1,t1)+dis(s2,t2)。

如果相交部分为(p1,p2),答案为p1,p2的最短路,加上p1,p2到其它4个点的最短路。

预处理任意点对距离,枚举两条路径重叠部分。