J. Graph and Cycles

Codeforces

IDCF10239J

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

There is an undirected weighted complete graph of $n$ vertices where $n$ is odd. Let's define a _cycle-array_ of size $k$ as an array of edges $[ e_1, e_2, \\dots, e_k ]$ that has the following properties: It is obvious that edges in a cycle-array form a cycle. Let's define $f (e_1, e_2)$ as a function that takes edges $e_1$ and $e_2$ as parameters and returns the maximum between the weights of $e_1$ and $e_2$. Let's say that we have a cycle-array $C = [ e_1, e_2, \\dots, e_k ]$. Let's define the _price of a cycle-array_ as the sum of $f (e_i, e_{i + 1})$ for all $i$ from $1$ to $k$ (consider $e_{k + 1} = e_1$). Let's define a _cycle-split_ of a graph as a set of non-intersecting cycle-arrays, such that the union of them contains all of the edges of the graph. Let's define the _price of a cycle-split_ as the sum of prices of the arrays that belong to it. There might be many possible cycle-splits of a graph. Given a graph, your task is to find the cycle-split with the minimum price and print the price of it. The first line contains one integer $n$ ($3 <= n <= 999$, $n$ is odd) — the number of nodes in the graph. Each of the following $frac(n dot.op (n -1), 2)$ lines contain three space-separated integers $u$, $v$ and $w$ ($1 <= u, v <= n, u eq.not v, 1 <= w <= 10^9$), meaning that there is an edge between the nodes $u$ and $v$ that has weight $w$. Print one integer — the minimum possible price of a cycle-split of the graph. Let's enumerate each edge in the same way as they appear in the input. I will use $e_i$ to represent the edge that appears $i$-th in the input. The only possible cycle-split in the first sample is $S = {[ e_1, e_2, e_3 ]}. " "f (e_1, e_2) + f (e_2, e_3) + f (e_3, e_1) = 1 + 1 + 1 = 3$. The optimal cycle-split in the second sample is $S = {[ e_3, e_8, e_9 ], [ e_2, e_4, e_7, e_{10}, e_5, e_1, e_6 ]}$. The price of $[ e_3, e_8, e_9 ]$ is equal to $12$, the price of $[ e_2, e_4, e_7, e_{10}, e_5, e_1, e_6 ]$ is equal to $23$, thus the price of the split is equal to $35$. ## Input The first line contains one integer $n$ ($3 <= n <= 999$, $n$ is odd) — the number of nodes in the graph.Each of the following $frac(n dot.op (n -1), 2)$ lines contain three space-separated integers $u$, $v$ and $w$ ($1 <= u, v <= n, u eq.not v, 1 <= w <= 10^9$), meaning that there is an edge between the nodes $u$ and $v$ that has weight $w$. ## Output Print one integer — the minimum possible price of a cycle-split of the graph. [samples] ## Note Let's enumerate each edge in the same way as they appear in the input. I will use $e_i$ to represent the edge that appears $i$-th in the input.The only possible cycle-split in the first sample is $S = {[ e_1, e_2, e_3 ]}. " "f (e_1, e_2) + f (e_2, e_3) + f (e_3, e_1) = 1 + 1 + 1 = 3$.The optimal cycle-split in the second sample is $S = {[ e_3, e_8, e_9 ], [ e_2, e_4, e_7, e_(10), e_5, e_1, e_6 ]}$. The price of $[ e_3, e_8, e_9 ]$ is equal to $12$, the price of $[ e_2, e_4, e_7, e_(10), e_5, e_1, e_6 ]$ is equal to $23$, thus the price of the split is equal to $35$.

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of files. Let $ x \in \mathbb{Z}^+ $ be the size (in GB) of each file. Let $ a \in \mathbb{Z}^+ $ be the capacity (in GB) of each flash memory. **Constraints** $ 1 \leq n \leq 10^5 $, $ 1 \leq x \leq a \leq 10^5 $. **Objective** Compute the minimum number of flash memories required to store all $ n $ files, where each file must be stored entirely in one flash memory, and no flash memory can exceed capacity $ a $. Let $ k = \left\lfloor \frac{a}{x} \right\rfloor $ be the maximum number of files that can be stored in one flash memory. Then the minimum number of flash memories needed is: $$ \left\lceil \frac{n}{k} \right\rceil $$

API Response (JSON)

{
  "problem": {
    "name": "J. Graph and Cycles",
    "description": {
      "content": "There is an undirected weighted complete graph of $n$ vertices where $n$ is odd. Let's define a _cycle-array_ of size $k$ as an array of edges $[ e_1, e_2, \\\\dots, e_k ]$ that has the following prope",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10239J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is an undirected weighted complete graph of $n$ vertices where $n$ is odd.\n\nLet's define a _cycle-array_ of size $k$ as an array of edges $[ e_1, e_2, \\\\dots, e_k ]$ that has the following prope...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of files.  \nLet $ x \\in \\mathbb{Z}^+ $ be the size (in GB) of each file.  \nLet $ a \\in \\mathbb{Z}^+ $ be the capacity (in GB) of each flash m...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments