分类： 网络流

YZOJ P4259 [FJWC 2019] 不同的缩写

YZOJ P4259 [FJWC 2019] 不同的缩写

时间限制：1000MS      内存限制：262144KB

出题人：E.Space      难度：\(6.1\)

  • 题目描述

在这个游戏中一共有 \(n\) 个角色。你需要编写一些关于这些角色的对话内容。

你打算用角色名字的一个非空子序列来作为它的简称。

当然，不同的角色要用不同的字符串作为简称，否则你就变量重名了。

你想确定一个简称的分配方案使得所有角色中最长的简称尽量短。

  • 输入格式

第一行一个正整数 \(n\)。

接下来 \(n\) 行，每行一个由小写字母组成的字符串，代表一个角色的名字。

不同的角色可能会有相同的名字。

  • 输出格式

如果不存在一种分配简称的方案满足条件，输出 \(-1\)。

否则第一行输出一个正整数，表示最长的简称的最小长度。

接下来 \(n\) 行每行一个字符串，按顺序表示每个角色的简称。

若有多种方案满足条件，那么你可以输出任意一种。

  • 样例输入

  • 样例输出

  • 数据规模与约定

保证 \(n \leq 300\) ，每个名字的长度不超过 \(300\)。

 

 

 …

YZOJ P2872 [POJ 1637]Sightseeing tour

YZOJ P2872 [POJ 1637]Sightseeing tour

Time Limit：1000MS      Memory Limit：131072KB

Difficulty: \(6.0\)

  • Description

The city executive board in Lund wants to construct a sightseeing tour by bus in Lund, so that tourists can see every corner of the beautiful city. They want to construct the tour so that every street in the city is visited exactly once. The bus should also start and end at the same junction. As in any city, the streets are either one-way or two-way, traffic rules that must be obeyed by the tour bus. Help the executive board and determine if it’s possible to construct a sightseeing tour under these constraints.

  • Input

On the first line of the input is a single positive integer n, telling the number of test scenarios to follow. Each scenario begins with a line containing two positive integers m and s, …

YZOJ P1868 土地划分

YZOJ P1868 土地划分

时间限制：1000MS      内存限制：131072KB

难度：\(5.1\)

  • 题目描述

在 \(Y\) 国有 \(N\) 座城市，并且有 \(M\) 条双向公路将这些城市连接起来，并且任意两个城市至少有一条路径可以互达。\(Y\) 国的国王去世之后，他的两个儿子 \(A\) 和 \(B\) 都想成为新的国王，但他们都想让这个国家更加安定，不会用武力解决问题。于是他们想将这个国家分成两个小国家 \(A\) 国和 \(B\) 国。现在，\(A\) 拥有 \(1\) 号城市，\(B\) 拥有 \(N\) 号城市，其他的城市还尚未确定归属哪边。

由于大家都想让国家变得更好，而某些城市的人民愿意国王的 \(A\) 儿子作为他们的领袖，而某些城市更看好 \(B\)，而为了交通的便捷，如果划分后的公路连接两个同一个国家的城市，那么更利于城市之间的交流。于是大臣们设计了一种对土地划分的评分机制，具体如下：

1，对于城市 \(i\) ，如果它划分给 \(A\) 国，将得到 \(VA[i]\) 的得分；划分给 \(B\) 国，将得到 \(VB[i]\) 的得分。

2，对于一条公路 \(i\) ，如果它连接两个 \(A\) 国的城市，将得到 \(EA[i]\) 的得分；连接两个 \(B\) 国的城市，将得到 \(EB[i]\) 的得分；否则，这条公路将失去意义，将扣除 \(EC[i]\) 的得分。

现请你找到最优的土地划分，使得这种它的评分最高。

  • 输入格式

第一行包含两个整数 \(N\)，\(M\)，含义如问题描述所示。

接下来一行 \(N-2\) 个非负整数，表示 \(VA[2..N-1]\) 。

接下来一行 \(N-2\) 个非负整数，表示 \(VB[2..N-1]\) 。

接下来 \(M\) 行，每行五个非负整数描述一条公路：\(X, Y, EA[i], EB[i], EC[i]\)，含义如问题描述所示。

  • 输出格式

输出一个整数，表示最高评分。

  • 样例输入

  • 样例输出

  • 数据规模与约定

\(100\%\) 的数据 \(N \leq 10000, M \leq 40000\)；

保证运算过程中及最终结果不超过32位带符号整数类型的表示范围。…

YZOJ P3049 [SHOI2010]Minimum Spanning Tree

YZOJ P3049 [SHOI2010]Minimum Spanning Tree

时间限制：1000MS      内存限制：262144KB

难度：\(6.0\)

  • 题目描述

有一个 \(n\) 个点，\(m\) 条边的无向图，每次可以对这张图进行操作：对于一条边 \((u,v)\)，可以把图中除了这条边以外的边，每一条的权值都减少 \(1\)。

对于某一条编号为 \(e\) 的边，至少需要多少次操作，才能保证其能出现在最小生成树中？

  • 输入格式

第一行输入三个整数 \(n\)、\(m\)、\(e\)。

接下来输入 \(m\) 行，每行输入三个整数，其中第 \(i+1\) 行输入的整数分别为 \(u_i\)、\(v_i\)、\(w_i\)，表示无向图的边的两个端点和边权。

  • 输出格式

输出一个整数表示答案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(50\%\) 的数据，\(n \leq 300\)，\(m \leq 1000\) 。

对于 \(100\%\) 的数据，\(n \leq 2 \times 10^4\)，\(m \leq 2 \times 10^5\)，\(0 \leq w_i \leq 2\times 10^4\) 。

 

 

 …