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 范围内

部分限制

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

Oops! 本题目还没有解答！

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

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

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