Skip to content

1257: 门票安排

题目

题目描述

某条铁路环线共有 $N$ 个车站,顺时针依次编号为 $1\dots N$。 该线路有 $N$ 种车票,分别编号为 $1\dots N$ 。一张车票 $i(1\leq i\leq N - 1)$ 仅供一人从车站 $i$ 顺时针移动到车站 $i+1$,或供一人从车站 $i+1$ 逆时针移动到车站 $i$ 。一张车票 $N$ 仅供一人从车站 $N$ 顺时针移动到车站 $1$ ,或供一人从车站 $1$ 逆时针移动到车站 $N$。 购买车票只有一种方法:购买套餐,套餐包含车票 $1\dots N$ 各 $1$ 张。 你是一名导游,你正在为游客订票。现有 $M$ 个订票请求,订票请求 $i(1\leq i\leq M)$ 表示从车站 $A_i$ 到车站 $B_i$ 有 $C_i$ 名旅客(路线可以不同)。 求最少需要购买多少套餐。

输入格式

第一行有两个整数 $N, M$,用空格分隔

在接下来的 $M$ 行中,第 $i$ 行 $(1\leq i\leq M)$ 有三个整数 $A_i, B_i, C_i$ ,用空格分隔

输出格式

一个整数,表示最少需要购买的套餐数

样例输入

样例输入 1

text 3 3 1 2 1 2 3 1 3 1 1

样例输入 2

text 3 2 1 2 4 1 2 2

样例输入 3

text 6 3 1 4 1 2 5 1 3 6 1

样例输出

样例输出 1

text 1

样例输出 2

text 3

样例输出 3

text 2

数据范围

时间限制:3000 ms 空间限制:256 mb

全局限制

  • $3 \leq N\leq 2\times 10^5$
  • $0 \leq M\leq 10^5$
  • $1 \leq A_i, B_i \leq N$
  • $C_i$ 在 int 范围内

部分限制

  1. $(\text{10 points})~C_i = 1 (1\leq i \leq M)$ 且 $N, M\leq 20$
  2. $(\text{35 points})~C_i = 1 (1\leq i \leq M)$ 且 $N, M\leq 300$
  3. $(\text{20 points})~C_i = 1 (1\leq i \leq M)$ 且 $N, M\leq 3000$
  4. $(\text{20 points})~C_i = 1 (1\leq i \leq M)$
  5. $(\text{15 points})$ 无限制

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!