官网提交

CF587D Duff in Mafia

题目描述

Duff 是她所在国家 Andarz Gu 的黑手党头目之一。Andarz Gu 有 $n$ 个城市（编号为 $1$ 到 $n$），通过 $m$ 条双向道路（编号为 $1$ 到 $m$）连接。

每条道路都有一个摧毁时间和一个颜色。第 $i$ 条道路连接城市 $v_i$ 和 $u_i$，颜色为 $c_i$，摧毁时间为 $t_i$。

黑手党想要摧毁 Andarz Gu 的一个匹配。一个匹配是若干道路的集合，集合中没有任何两条道路有公共端点。他们可以并行炸毁这些道路，即总摧毁时间为所有被选择道路的最大摧毁时间。

他们希望满足以下两个条件：

1. 剩余道路形成一个合法着色。
2. 匹配的摧毁时间最小。

所谓剩余道路形成合法着色，就是任何两个同色的道路没有公共端点，换句话说，每种颜色的边都构成一个匹配。

黑手党中没人会编程，所以 Duff 向你寻求帮助。请你帮助她判断是否有可能满足上述条件，并求出该匹配（或指出不可能）。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 5 \times 10^4$，$1 \le m \le 5 \times 10^4$），分别表示城市数和道路数。

接下来的 $m$ 行，每行包含四个整数 $v_i, u_i, c_i, t_i$（$1 \le v_i,u_i \le n$，$v_i \ne u_i$，$1 \le c_i, t_i \le 10^9$，$1 \le i \le m$），分别表示第 $i$ 条道路连接的城市编号、颜色和摧毁时间。

输出格式

第一行输出若能满足第一个条件则输出 “Yes”，否则输出 “No”。

若可以，请在第二行输出两个整数 $t$ 和 $k$，其中 $t$ 为最小摧毁时间，$k$ 为要摧毁道路的数量。

第三行输出 $k$ 个两两不同的整数，表示要摧毁的道路编号（从 1 开始，按输入顺序编号），顺序任意。

如果有多组解，输出任意一组均可。

输入输出样例 #1

输入 #1

5 7
2 1 3 7
3 1 1 6
5 4 1 8
4 5 1 1
3 2 2 3
4 5 2 5
2 3 2 4

输出 #1

Yes
3 2
4 5

输入输出样例 #2

输入 #2

3 5
3 2 1 3
1 3 1 1
3 2 1 4
1 3 2 2
1 3 2 10

输出 #2

No

说明/提示

第一个样例的 Andarz Gu 的图如下：

一种方案是摧毁带有叉号的道路。

第二个样例的 Andarz Gu 的图如下：

由 ChatGPT 5 翻译