发布于

USACO 草鉴定Grass Cownoisseur

In an effort to better manage the grazing patterns of his cows, Farmer John has installed one-way cow paths all over his farm. The farm consists of N fields, conveniently numbered 1..N, with each one-way cow path connecting a pair of fields. For example, if a path connects from field X to field Y, then cows are allowed to travel from X to Y but not from Y to X.

Bessie the cow, as we all know, enjoys eating grass from as many fields as possible. She always starts in field 1 at the beginning of the day and visits a sequence of fields, returning to field 1 at the end of the day. She tries to maximize the number of distinct fields along her route, since she gets to eat the grass in each one (if she visits a field multiple times, she only eats the grass there once).

As one might imagine, Bessie is not particularly happy about the one-way restriction on FJ’s paths, since this will likely reduce the number of distinct fields she can possibly visit along her daily route. She wonders how much grass she will be able to eat if she breaks the rules and follows up to one path in the wrong direction. Please compute the maximum number of distinct fields she can visit along a route starting and ending at field 1, where she can follow up to one path along the route in the wrong direction. Bessie can only travel backwards at most once in her journey. In particular, she cannot even take the same path backwards twice.

INPUT: (file grass.in)

The first line of input contains N and M, giving the number of fields and the number of one-way paths (1 <= N, M <= 100,000).

The following M lines each describe a one-way cow path. Each line contains two distinct field numbers X and Y, corresponding to a cow path from X to Y. The same cow path will never appear more than once.

OUTPUT: (file grass.out)

A single line indicating the maximum number of distinct fields Bessie

can visit along a route starting and ending at field 1, given that she can

follow at most one path along this route in the wrong direction.

四句话题解(非常简单)：

Tarjan瞎缩一波点

然后单原SPFA求点1能到的点的答案贡献

然后跑单汇SPFA求能到点1的点的答案贡献

最后枚举反边判相连求答案

 

发布于

BZOJ1924 | SDOI2010 所驼门王的宝藏

在宽广的非洲荒漠中，生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的Alpaca L. Sotomon是这个家族的领袖，外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐，他曾亲自率军粉碎河蟹帝国主义的野蛮侵略，为族人立下赫赫战功。所驼门王一生财宝无数，但因其生性节俭低调，他将财宝埋藏在自己设计的地下宫殿里，这也是今天Henry Curtis故事的起点。Henry是一个爱财如命的贪婪家伙，而又非常聪明，他费尽心机谋划了这次盗窃行动，破解重重机关后来到这座地下宫殿前。

整座宫殿呈矩阵状，由R×C间矩形宫室组成，其中有N间宫室里埋藏着宝藏，称作藏宝宫室。宫殿里外、相邻宫室间都由坚硬的实体墙阻隔，由一间宫室到达另一间只能通过所驼门王独创的移动方式——传送门。所驼门王为这N间藏宝宫室每间都架设了一扇传送门，没有宝藏的宫室不设传送门，所有的宫室传送门分为三种：

  1. “横天门”：由该门可以传送到同行的任一宫室；
  2. “纵寰门”：由该门可以传送到同列的任一宫室；
  3. “自由门”：由该门可以传送到以该门所在宫室为中心周围8格中任一宫室（如果目标宫室存在的话）。

深谋远虑的Henry当然事先就搞到了所驼门王当年的宫殿招标册，书册上详细记录了每扇传送门所属宫室及类型。而且，虽然宫殿内外相隔，但他自行准备了一种便携式传送门，可将自己传送到殿内任意一间宫室开始寻宝，并在任意一间宫室结束后传送出宫。整座宫殿只许进出一次，且便携门无法进行宫室之间的传送。不过好在宫室内传送门的使用没有次数限制，每间宫室也可以多次出入。

现在Henry已经打开了便携门，即将选择一间宫室进入。为得到尽多宝藏，他希望安排一条路线，使走过的不同藏宝宫室尽可能多。请你告诉Henry这条路线最多行经不同藏宝宫室的数目。

 

[无耻地借用洛谷的图片]

首先缩一下点……

然后跑DP……

很简单QAQ

在BZOJ写了7000B，成功拿到『最近几页的最长代码』成就

在洛谷跑了400ms，超级快。//好像空间还用的很少

发布于

CodeVS&Luogu 间谍网络

这个题大概思路就是一发裸的Tarjan然后建一个缩点的图。

读入之后先来一发Tarjan（注意有可能有多个连通图），记录下每个点属于的强连通分量。

然后缩点，建一个DAG，这时根据DAG的结构，肯定存在若干入度为0的点

下面就是重点了，只需要收买（也就是计算这个强连通分量中Minimize的Money）所有入度为0的缩点，(根结点)就一定可以抓完 全图的 间谍。

假如收买了根点之后无法收买缩点u，那么缩点u一定不是根点的子结点，也就意味着u绝对不和这个DAG联通，那u的入度为0（U肯定也是根结点），就要收买u，所以收买所有根点是可以抓整个DAG的间谍的。

所以，当根点无法被收买的时候，那无解，统计一下无法被收买的强连通分量（也就是根点）之中最小的点，然后输出即可

或者，有解，那么就统计根点的最小花费，加起来就OK。

不需要DFS/BFS。统计的时候可以玩枚举（强连通分量不会太多……）