POJ 1201 Intervals【差分约束】

传送门:http://poj.org/problem?id=1201

题意:

有n个如下形式的条件:POJ 1201 Intervals【差分约束】,表示在区间[POJ 1201 Intervals【差分约束】, POJ 1201 Intervals【差分约束】]内至少要选择POJ 1201 Intervals【差分约束】个整数点.问你满足以上所有条件,最少需要选多少个点?

思路:第一道差分约束题,有关差分约束知识详见https://blog.csdn.net/whereisherofrom/article/details/78922648(个人感觉这个博主写的挺好的)

POJ 1201 Intervals【差分约束】表示从区间[0,x]中选择的整数点个数,则有POJ 1201 Intervals【差分约束】=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">(因为POJ 1201 Intervals【差分约束】=0" class="mathcode" src="//bbsmax.ikafan.com/static/L3Byb3h5L2h0dHBzL3ByaXZhdGUuY29kZWNvZ3MuY29tL2dpZi5sYXRleD9hX2k=.jpg%3E%3D0">,会出现数组下标为-1的情况),如果只靠这个式子是无法得出答案的,题中还有隐藏的约束POJ 1201 Intervals【差分约束】即是POJ 1201 Intervals【差分约束】=0" class="mathcode" src="https://private.codecogs.com/gif.latex?s_%7Bi+1%7D-s_i%3E%3D0">和POJ 1201 Intervals【差分约束】=-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;
}
上一篇:POJ 1201 Intervals(差分约束 区间约束模版)


下一篇:每天一个linux命令(61):vi命令 /企业常用的linux命令清单