传送门:http://poj.org/problem?id=1201
题意:
有n个如下形式的条件:,表示在区间[, ]内至少要选择个整数点.问你满足以上所有条件,最少需要选多少个点?
思路:第一道差分约束题,有关差分约束知识详见https://blog.csdn.net/whereisherofrom/article/details/78922648(个人感觉这个博主写的挺好的)
令表示从区间[0,x]中选择的整数点个数,则有=c_i\rightarrow s_{b_i+1}-s_{a_i}>=c_i" class="mathcode" src="https://private.codecogs.com/gif.latex?s_%7Bb_i%7D-s_%7Ba_i-1%7D%3E%3Dc_i%5Crightarrow%20s_%7Bb_i+1%7D-s_%7Ba_i%7D%3E%3Dc_i">(因为=0" class="mathcode" src="//bbsmax.ikafan.com/static/L3Byb3h5L2h0dHBzL3ByaXZhdGUuY29kZWNvZ3MuY29tL2dpZi5sYXRleD9hX2k=.jpg%3E%3D0">,会出现数组下标为-1的情况),如果只靠这个式子是无法得出答案的,题中还有隐藏的约束即是=0" class="mathcode" src="https://private.codecogs.com/gif.latex?s_%7Bi+1%7D-s_i%3E%3D0">和=-1" class="mathcode" src="https://private.codecogs.com/gif.latex?s_i-s_%7Bi+1%7D%3E%3D-1">,题中要求最小值,所以用spfa跑一遍最长路即可。
代码:
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 50005;
const int INF = 0x3f3f3f3f;
int tot;
struct node
{
int to;
int next;
int w;
};
node edges[maxn * 3];
int head[maxn];
int d[maxn];
bool vis[maxn];
void add_edges(int u, int v, int w)
{
edges[++tot].to = v;
edges[tot].w = w;
edges[tot].next = head[u];
head[u] = tot;
}
int l = 50005;
int r = -1;
void spfa()
{
for(int i = l; i <= r; i++)
vis[i] = false, d[i] = -INF;
d[l] = 0;
queue<int>q;
q.push(l);
while(!q.empty())
{
int x = q.front();
q.pop();
vis[x] = false;
for(int i = head[x]; i; i = edges[i].next)
{
node v = edges[i];
if(d[v.to] < d[x] + v.w)
{
d[v.to] = d[x] + v.w;
if(!vis[v.to])
{
vis[v.to] = true;
q.push(v.to);
}
}
}
}
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add_edges(a, b + 1, c);
r = max(r, b + 1); //求区间右端点
l = min(l, a); //求区间左端点
}
for(int i = l; i < r; i++)
{
add_edges(i + 1, i, -1);
add_edges(i, i + 1, 0);
}
spfa();
cout << d[r] << endl;
}