# 负环

Acwing1165 单词环

原题链接:Acwing1165

题目描述:我们有 n 个字符串,每个字符串都是由 a∼z 的小写英文字母组成的。

如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两个字符相匹配,那么我们称 A 与 B 能够相连(注意:A 能与 B 相连不代表 B 能与 A 相连)。

我们希望从给定的字符串中找出一些,使得它们首尾相连形成一个环串(一个串首尾相连也算),我们想要使这个环串的平均长度最大。

……

READ MORE

Acwing361 观光奶牛

原题链接:Acwing361

题目描述:给定一张 L 个点、 P 条边的有向图,每个点都有一个权值 $f[i]$,每条边都有一个权值 $t[i]$。

求图中的一个环,使“环上各点的权值之和”除以“环上各边的权值之和”最大。

输出这个最大值。

注意:数据保证至少存在一个环。

……

READ MORE

Recents
Categories
Tags
Links