[CCPC 2023 北京市赛] 最小环

{
  "problem": {
    "name": "[CCPC 2023 北京市赛] 最小环",
    "description": {
      "content": "小 I 发明了 $O(n + m)$ 的有向图最小环，于是他想考考你。 给定一个 $n$ 个节点、$m$ 条边的有向图，每条边有正整数边权。你需要求出图上的一个环使得环上边的边权和最小。求出这个最小值，或者报告不存在环。 当然，由于你不会 $O(n + m)$ 的有向图最小环，于是小 I 放宽了条件：保证输入的图是弱连通的，且 $m-n$ 不会很大。一个图是弱连通的当且仅当将有向边换为无向边后",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10044"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 I 发明了 $O(n + m)$ 的有向图最小环，于是他想考考你。\n\n给定一个 $n$ 个节点、$m$ 条边的有向图，每条边有正整数边权。你需要求出图上的一个环使得环上边的边权和最小。求出这个最小值，或者报告不存在环。\n\n当然，由于你不会 $O(n + m)$ 的有向图最小环，于是小 I 放宽了条件：保证输入的图是弱连通的，且 $m-n$ 不会很大。一个图是弱连通的当且仅当将有向边换为无向边后...",
      "is_translate": false,
      "language": "English"
    }
  ]
}