差分约束Tag:

POJ 1201 Intervals

MayFlyyh | 最短路 | 2018-08-11
题意:给m个区间li,ri,再给一个ci,要求在每个区间li-ri种至少选ci个数,求满足条件最小选的数字。 数字值域:0~50000,m<=50000 哎,考虑差分约束,设D[i]表示从0-i满足条件至少选多少个 l-r,至少选C个,即D[r]-D[l-1]>=c,从l-1到r连一条权值为c的边 然后隐藏条件:0<=D[i]-D[i-1]<=1 然后呢?选一个最小的li,跑向最大的ri。 ... [阅读全文]
Ɣ回顶部