[DTCPC 2024] 环

Luogu

IDLGP10166

Time1000ms

Memory512MB

DifficultyP3

贪心2024拓扑排序洛谷月赛

给定无重边无自环的有向图 $G$ 和序列 $\{a_n\}$，每次可以花费 $a_i+a_j$ 的代价加上一条 $i\to j$ 的边，试花费最小代价使得可以找到 $k\geq 2$ 个不同的点 $p_1,p_2,\dots,p_k$，满足 $\forall i\in [1,k]$，都有一条 $p_i\to p_{i\bmod k+1}$ 的边。 ## Input 第一行两个整数 $n,m$（$2\le n\le 5 \times 10^5$，$n-1 \le m \le 10^6$），表示图的点数和边数。第二行输入 $n$ 个整数，表示序列 $\{a_n\}$（$1\le a_i\le 10^9$）。接下来 $m$ 行，每行两个整数 $u,v$（$1\le u,v\le n$），表示存在一条有向边 $u\to v$。 ## Output 一行一个整数表示最小代价。 [samples] ## Background 环

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[DTCPC 2024] 环",
    "description": {
      "content": "给定无重边无自环的有向图 $G$ 和序列 $\\{a_n\\}$，每次可以花费 $a_i+a_j$ 的代价加上一条 $i\\to j$ 的边，试花费最小代价使得可以找到 $k\\geq 2$ 个不同的点 $p_1,p_2,\\dots,p_k$，满足 $\\forall i\\in [1,k]$，都有一条 $p_i\\to p_{i\\bmod k+1}$ 的边。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10166"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定无重边无自环的有向图 $G$ 和序列 $\\{a_n\\}$，每次可以花费 $a_i+a_j$ 的代价加上一条 $i\\to j$ 的边，试花费最小代价使得可以找到 $k\\geq 2$ 个不同的点 $p_1,p_2,\\dots,p_k$，满足 $\\forall i\\in [1,k]$，都有一条 $p_i\\to p_{i\\bmod k+1}$ 的边。\n\n## Input\n\n第一行两个整数 $n,m$（...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments