poj 1201 Intervals(差分约束)

题目:http://poj.org/problem?id=1201

题意:给定n组数据,每组有ai,bi,ci,要求在区间[ai,bi]内至少找ci个数, 并使得找的数字组成的数组Z的长度最小。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std; const int INF = <<;
struct node
{
int u;
int v;
int w;
int next;
}edge[];
int dis[];
int mi,ma,n; void bellman_ford()
{
int i,f=;
while(f)
{
f=;
for(i=; i<=n; i++)
if(dis[edge[i].u]>dis[edge[i].v]-edge[i].w)
{
dis[edge[i].u]=dis[edge[i].v]-edge[i].w;
f=;
} for(i=mi; i<=ma; i++)
if(dis[i]>dis[i-]+)
{
dis[i]=dis[i-]+;
f=;
} for(i=ma; i>=mi; i--)
if(dis[i-]>dis[i])
{
dis[i-]=dis[i];
f=;
}
}
} int main()
{
int i;
while(~scanf("%d",&n))
{
mi=INF; ma=-;
for(i=; i<=n; i++)
{
scanf("%d%d%d",&edge[i].u, &edge[i].v, &edge[i].w);
if(mi>edge[i].u)
mi=edge[i].u;
if(ma<edge[i].v)
ma=edge[i].v; edge[i].u--;
dis[i]=;
}
bellman_ford();
printf("%d\n",dis[ma]-dis[mi-]);
}
return ;
}

大神的题解:

差分约束的思想:可以肯定的是s[bi]-s[ai-1]>=ci; 为什么要ai-1,是因为ai也要选进来
在一个是s[i]-s[i-1]<=1;
s[i]-s[i-1]>=0
所以整理上面三个式子可以得到约束条件:
①s[ai-1]-s[bi] <= -ci
②s[i]-s[i-1] <= 1
③s[i-1]-s[i] <= 0

1、约束条件必须同为<= 或者同为>=

2、若形如:x1 - x2<=k1   则 x2点 向x1点连边,权值为k1,求最短路

若形如:x1-x2>=k1      则 x2点 向x1点连边,权值为k1,求最长路

3、如果多组约束存在矛盾,则图中存在负环,判断负环的方法是用spfa判断是否有点进队次数>=n

上一篇:poj 1201 Intervals——差分约束裸题


下一篇:poj 1201 Intervals(差分约束)