F. Best Edge Weight

Codeforces

IDCF828F

Time2000ms

Memory256MB

Difficulty—

data structuresgraphs

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 weights $ w: E \to \mathbb{Z}^+ $. Let $ e_i \in E $ denote the $ i $-th edge in input order, with endpoints $ u_i, v_i $ and initial weight $ c_i $. **Constraints** 1. $ 2 \leq n \leq 2 \cdot 10^5 $ 2. $ n - 1 \leq m \leq 2 \cdot 10^5 $ 3. No loops or multiple edges. 4. All weights $ c_i \in [1, 10^9] $. **Objective** For each edge $ e_i \in E $, compute the maximum integer weight $ w_{\max}(e_i) $ such that $ e_i $ is contained in *every* minimum spanning tree (MST) of $ G $, when $ w(e_i) $ is set to $ w_{\max}(e_i) $ and all other edge weights remain unchanged. If no such finite maximum exists (i.e., $ e_i $ is in every MST regardless of weight), output $ -1 $. **Note**: Edges are processed independently; only one edge’s weight is modified at a time.

Samples

Input #1

Output #1

2 2 2 1

Input #2

Output #2

\-1 -1 -1

API Response (JSON)

{
  "problem": {
    "name": "F. 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": "CF828F"
  },
  "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 weights $ w: E \\to \\mathbb{Z}^+ $.  \nLet $ e_i \\in E $ denote the $ i $-th edge ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments