F. Royal Questions

Codeforces

IDCF875F

Time1000ms

Memory512MB

Difficulty—

dsugraphsgreedy

English · Original

Chinese · Translation

Formal · Original

In a medieval kingdom, the economic crisis is raging. Milk drops fall, Economic indicators are deteriorating every day, money from the treasury disappear. To remedy the situation, King Charles Sunnyface decided make his _n_ sons-princes marry the brides with as big dowry as possible. In search of candidates, the king asked neighboring kingdoms, and after a while several delegations arrived with _m_ unmarried princesses. Receiving guests, Karl learned that the dowry of the _i_ th princess is _w__i_ of golden coins. Although the action takes place in the Middle Ages, progressive ideas are widespread in society, according to which no one can force a princess to marry a prince whom she does not like. Therefore, each princess has an opportunity to choose two princes, for each of which she is ready to become a wife. The princes were less fortunate, they will obey the will of their father in the matter of choosing a bride. Knowing the value of the dowry and the preferences of each princess, Charles wants to play weddings in such a way that the total dowry of the brides of all his sons would be as great as possible. At the same time to marry all the princes or princesses is not necessary. Each prince can marry no more than one princess, and vice versa, each princess can marry no more than one prince. Help the king to organize the marriage of his sons in the most profitable way for the treasury. ## Input The first line contains two integers _n_, _m_ (2 ≤ _n_ ≤ 200 000, 1 ≤ _m_ ≤ 200 000) — number of princes and princesses respectively. Each of following _m_ lines contains three integers _a__i_, _b__i_, _w__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_, _a__i_ ≠ _b__i_, 1 ≤ _w__i_ ≤ 10 000) — number of princes, which _i_\-th princess is ready to marry and the value of her dowry. ## Output Print the only integer — the maximum number of gold coins that a king can get by playing the right weddings. [samples]

在中世纪的一个王国中，经济危机正在肆虐。牛奶滴落，经济指标每日恶化，国库中的金钱不断消失。为扭转局势，查尔斯国王决定让他的 #cf_span[n] 个王子儿子们迎娶嫁妆尽可能丰厚的公主。为寻找候选人，国王向邻国发出邀请，不久后有 #cf_span[m] 位未婚公主的使团抵达。接待宾客时，查尔斯得知第 #cf_span[i] 位公主的嫁妆为 #cf_span[wi] 枚金币。尽管事件发生在中世纪，但社会中广泛流行进步思想：没有人能强迫一位公主嫁给她不喜欢的王子。因此，每位公主都有权选择两位王子，她愿意成为其中任何一位的妻子。而王子们则没那么幸运，他们在择偶问题上必须服从父亲的意愿。在已知每位公主的嫁妆价值和偏好前提下，查尔斯希望安排婚礼，使得他所有儿子的 brides 的总嫁妆尽可能大。同时，并不一定要让所有王子或公主都结婚。每位王子最多只能娶一位公主，反之亦然，每位公主最多只能嫁给一位王子。请帮助国王以对国库最有利的方式安排他儿子们的婚事。第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[2 ≤ n ≤ 200 000], #cf_span[1 ≤ m ≤ 200 000]) —— 分别表示王子和公主的数量。接下来的 #cf_span[m] 行中，每行包含三个整数 #cf_span[ai], #cf_span[bi], #cf_span[wi] (#cf_span[1 ≤ ai, bi ≤ n], #cf_span[ai ≠ bi], #cf_span[1 ≤ wi ≤ 10 000]) —— 表示第 #cf_span[i] 位公主愿意嫁给的两位王子编号及其嫁妆价值。 ## Input 第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[2 ≤ n ≤ 200 000], #cf_span[1 ≤ m ≤ 200 000]) —— 分别表示王子和公主的数量。接下来的 #cf_span[m] 行中，每行包含三个整数 #cf_span[ai], #cf_span[bi], #cf_span[wi] (#cf_span[1 ≤ ai, bi ≤ n], #cf_span[ai ≠ bi], #cf_span[1 ≤ wi ≤ 10 000]) —— 表示第 #cf_span[i] 位公主愿意嫁给的两位王子编号及其嫁妆价值。 ## Output 请输出一个整数 —— 国王通过合理安排婚礼所能获得的最大金币数量。 [samples]

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ denote the number of princes and princesses, respectively. Let $ P = \{1, 2, \dots, n\} $ be the set of princes. Let $ R = \{1, 2, \dots, m\} $ be the set of princesses. For each princess $ i \in R $, let $ (a_i, b_i, w_i) \in P \times P \times \mathbb{Z}^+ $ denote the two princes she accepts and her dowry, with $ a_i \ne b_i $. **Constraints** 1. $ 2 \le n \le 200{,}000 $ 2. $ 1 \le m \le 200{,}000 $ 3. $ 1 \le w_i \le 10{,}000 $ for all $ i \in R $ 4. Each prince can marry at most one princess. 5. Each princess can marry at most one prince. **Objective** Find a matching $ M \subseteq R $ (a subset of princesses assigned to princes) such that: - For each $ i \in M $, princess $ i $ is matched to exactly one of $ a_i $ or $ b_i $, - No prince is matched to more than one princess, - The total dowry $ \sum_{i \in M} w_i $ is maximized. **Output** The maximum total dowry achievable under the above constraints.

Samples

Input #1

Output #1

Input #2

3 2
1 2 10
3 2 20

Output #2

API Response (JSON)

{
  "problem": {
    "name": "F. Royal Questions",
    "description": {
      "content": "In a medieval kingdom, the economic crisis is raging. Milk drops fall, Economic indicators are deteriorating every day, money from the treasury disappear. To remedy the situation, King Charles Sunnyfa",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF875F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In a medieval kingdom, the economic crisis is raging. Milk drops fall, Economic indicators are deteriorating every day, money from the treasury disappear. To remedy the situation, King Charles Sunnyfa...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在中世纪的一个王国中，经济危机正在肆虐。牛奶滴落，经济指标每日恶化，国库中的金钱不断消失。为扭转局势，查尔斯国王决定让他的 #cf_span[n] 个王子儿子们迎娶嫁妆尽可能丰厚的公主。\n\n为寻找候选人，国王向邻国发出邀请，不久后有 #cf_span[m] 位未婚公主的使团抵达。接待宾客时，查尔斯得知第 #cf_span[i] 位公主的嫁妆为 #cf_span[wi] 枚金币。\n\n尽管事件发生在中...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of princes and princesses, respectively.  \nLet $ P = \\{1, 2, \\dots, n\\} $ be the set of princes.  \nLet $ R = \\{1, 2, \\dots, m\\} $ be t...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments