#P6295. 「JOISC 2017 Day 2」门票安排

    ID: 5784 传统题 4000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-二分答案一维差分有限候选集缩减堆贪心交换论证

「JOISC 2017 Day 2」门票安排

题目描述

题目译自 JOISC 2017 Day2 T1「切符の手配 / Arranging Tickets」

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

输入格式

第一行有两个整数 N,MN,M,用空格分隔。
在接下来的 MM 行中,第 ii 行 (1≤i≤M)(1\le i\le M) 有三个整数 Ai,Bi,CiA_i,B_i,C_i,用空格分隔。

输出格式

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

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

数据范围与提示

Subtask # 分值 NN MM Ci(1≤i≤M)C_i(1\le i\le M)
1 10 N≤20N\le 20 M≤20M\le 20 Ci=1C_i=1
2 35 N≤300N\le 300 M≤300M\le 300
3 20 N≤3000N\le 3000 M≤3000M\le 3000
4 N≤2×105N\le 2\times 10^5 M≤105M\le 10^5
5 15 Ci≤109C_i \leq 10^9