D. Best Edge Weight

Codeforces

IDCF827D

Time2000ms

Memory256MB

Difficulty—

data structuresdfs and similargraphstrees

English · Original

Chinese · Translation

Formal · Original

You are given a connected weighted graph with _n_ vertices and _m_ edges. The graph doesn't contain loops nor multiple edges. Consider some edge with id _i_. Let's determine for this edge the maximum integer weight we can give to it so that it is contained in all minimum spanning trees of the graph if we don't change the other weights. You are to determine this maximum weight described above for each edge. You should calculate the answer for each edge independently, it means there can't be two edges with changed weights at the same time. ## Input The first line contains two integers _n_ and _m_ (2 ≤ _n_ ≤ 2·105, _n_ - 1 ≤ _m_ ≤ 2·105), where _n_ and _m_ are the number of vertices and the number of edges in the graph, respectively. Each of the next _m_ lines contains three integers _u_, _v_ and _c_ (1 ≤ _v_, _u_ ≤ _n_, _v_ ≠ _u_, 1 ≤ _c_ ≤ 109) meaning that there is an edge between vertices _u_ and _v_ with weight _c_. ## Output Print the answer for each edge in the order the edges are given in the input. If an edge is contained in every minimum spanning tree with any weight, print _\-1_ as the answer. [samples]

[{"iden":"statement","content":"给定一个具有 #cf_span[n] 个顶点和 #cf_span[m] 条边的连通加权图。图中不含自环和重边。考虑一条编号为 #cf_span[i] 的边，我们需要确定可以赋予它的最大整数权重，使得在不改变其他边权重的情况下，该边包含在图的所有最小生成树中。\n\n你需要为每条边计算上述的最大权重。你应该独立地计算每条边的答案，即不能同时修改两条边的权重。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 2·105]，#cf_span[n - 1 ≤ m ≤ 2·105]），分别表示图的顶点数和边数。\n\n接下来的 #cf_span[m] 行每行包含三个整数 #cf_span[u]、#cf_span[v] 和 #cf_span[c]（#cf_span[1 ≤ v, u ≤ n]，#cf_span[v ≠ u]，#cf_span[1 ≤ c ≤ 109]），表示顶点 #cf_span[u] 和 #cf_span[v] 之间有一条权重为 #cf_span[c] 的边。\n\n请按输入中边的顺序输出每条边的答案。如果某条边在任意权重下都包含在所有最小生成树中，则输出 _-1_。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 2·105]，#cf_span[n - 1 ≤ m ≤ 2·105]），分别表示图的顶点数和边数。接下来的 #cf_span[m] 行每行包含三个整数 #cf_span[u]、#cf_span[v] 和 #cf_span[c]（#cf_span[1 ≤ v, u ≤ n]，#cf_span[v ≠ u]，#cf_span[1 ≤ c ≤ 109]），表示顶点 #cf_span[u] 和 #cf_span[v] 之间有一条权重为 #cf_span[c] 的边。"},{"iden":"output","content":"请按输入中边的顺序输出每条边的答案。如果某条边在任意权重下都包含在所有最小生成树中，则输出 _-1_。"},{"iden":"examples","content":"输入\n4 4\n1 2 2\n2 3 2\n3 4 2\n4 1 3\n输出\n2 2 2 1 \n\n输入\n4 3\n1 2 2\n2 3 2\n3 4 2\n输出\n-1 -1 -1 "}]}

**Definitions** Let $ G = (V, E) $ be a connected, undirected, weighted graph with $ |V| = n $, $ |E| = m $, and edge set $ E = \{e_1, e_2, \dots, e_m\} $, where each edge $ e_i = (u_i, v_i, w_i) $ has weight $ w_i \in \mathbb{Z}^+ $. Let $ \mathcal{T} $ denote the set of all minimum spanning trees (MSTs) of $ G $. For each edge $ e_i \in E $, define $ W_{\max}(e_i) $ as the maximum real number $ x $ such that if $ w_i $ is replaced by $ x $, then $ e_i $ is contained in *every* MST of the modified graph, while all other edge weights remain unchanged. **Constraints** 1. $ 2 \le n \le 2 \cdot 10^5 $ 2. $ n - 1 \le m \le 2 \cdot 10^5 $ 3. For all $ i \in \{1, \dots, m\} $: $ 1 \le w_i \le 10^9 $ 4. $ G $ has no loops or multiple edges. **Objective** For each edge $ e_i \in E $, compute: $$ W_{\max}(e_i) = \begin{cases} -1 & \text{if } e_i \text{ is in every MST of } G \text{ for any weight } x \ge 1, \\ \max \{ x \in \mathbb{R} \mid e_i \in T \text{ for all } T \in \mathcal{T}_x \} & \text{otherwise}, \end{cases} $$ where $ \mathcal{T}_x $ is the set of MSTs of the graph with $ w_i $ replaced by $ x $, and all other weights unchanged.

Samples

Input #1

Output #1

2 2 2 1

Input #2

Output #2

\-1 -1 -1

API Response (JSON)

{
  "problem": {
    "name": "D. Best Edge Weight",
    "description": {
      "content": "You are given a connected weighted graph with _n_ vertices and _m_ edges. The graph doesn't contain loops nor multiple edges. Consider some edge with id _i_. Let's determine for this edge the maximum ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF827D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a connected weighted graph with _n_ vertices and _m_ edges. The graph doesn't contain loops nor multiple edges. Consider some edge with id _i_. Let's determine for this edge the maximum ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"给定一个具有 #cf_span[n] 个顶点和 #cf_span[m] 条边的连通加权图。图中不含自环和重边。考虑一条编号为 #cf_span[i] 的边，我们需要确定可以赋予它的最大整数权重，使得在不改变其他边权重的情况下，该边包含在图的所有最小生成树中。\\n\\n你需要为每条边计算上述的最大权重。你应该独立地计算每条边的答案，即不能...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be a connected, undirected, weighted graph with $ |V| = n $, $ |E| = m $, and edge set $ E = \\{e_1, e_2, \\dots, e_m\\} $, where each edge $ e_i = (u_i, v_i, w_i) $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments