邻接表 – Tgotp-Blog

1269 迷宫城堡

Problem Description
为了训练小希的方向感,Gardon建立了一座大城堡,里面有N个房间(N<=10000)和M条通道(M<=100000),每个通道都是单向的,就是说若称某通道连通了A房间和B房间,只说明可以通过这个通道由A房间到达B房间,但并不说明通过它可以由B房[......]

Read more

bzoj1006 P3196 [HNOI2008]神奇的国度

思路:弦图

算法:mcs,邻接表

具体实现:逆序寻找完美消除序列,然后染成能染的最小颜色,证明参见cdq的弦图与区间课件。

c++代码:

 

Educational Codeforces Round 22 C

题面

C. The Tag Game
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

[......]

Read more

1999: [Noip2007]Core树网的核

【题目大意】

求无根树的直径上一段不超过S长的链,使得偏心距最小。具体概念见原题

【思路】

首先明确几个性质:

(1)对于树中的任意一点,距离其最远的点一定是树的直径的某一端点。

(2)所有的直径是等价的,即任意一条所能求出的该最小偏心距相等。

于是我们可以用两[......]

Read more