poj 1201(差分约束)

poj 1201
差分约束。
设$dis[i]$为$[1,i]$包含在$Z$集合内数的个数
由题意得,$dis[b]-dis[a-1]\ge c$,
由隐含条件每个数只出现一次或不出现,得$0 \le dis[i]-dis[i-1] \le 1$
整理后得,
$$
dis[b]-dis[a-1]\ge c \\
dis[i]-dis[i-1]\ge 0 \\
dis[i-1]-dis[i]\ge -1
$$
然后按照差分约束系统用SPFA求最长路即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
const int MAXN = 50000 + 5;
struct edge
{
int u, v, c;
}E[MAXN*3*2];
vector<int> G[MAXN*2];
int e_num;
int n;
int minr = 100000000, maxr = -minr;
void addE(int u, int v, int c)
{
e_num++;
E[e_num].u = u;
E[e_num].v = v;
E[e_num].c = c;
G[u].push_back(e_num);
}
int dis[MAXN*2];
int vi[MAXN*2];
void spfa()
{
ms(dis, -(127/3));
ms(vi, false);
queue<int> q;
q.push(minr); dis[minr] = 0;
while (!q.empty())
{
int r = q.front(); q.pop();
vi[r] = false;
for (int i=0;i<G[r].size();i++)
{
edge ed = E[G[r][i]];
if (dis[ed.v]<dis[r]+ed.c)
{
dis[ed.v] = dis[r] + ed.c;
if (!vi[ed.v])
{
vi[ed.v] = true;
q.push(ed.v);
}
}
}
}
}
int main()
{
while (scanf("%d", &n)==1)
{
e_num = 0;
for (int i=1;i<=n;i++)
{
int ai,bi,ci;
scanf("%d%d%d", &ai, &bi, &ci);
//dis[bi]-dis[ai-1]>=ci
addE(ai-1, bi, ci);
minr = min(minr, ai-1);
maxr = max(maxr, bi);
}
for (int i=minr+1;i<=maxr;i++)
{
//0<=dis[i]-dis[i-1]<=1
//dis[i]-dis[i-1]>=0
addE(i-1, i, 0);
//dis[i]-dis[i-1]<=1
//dis[i-1]-dis[i]>=-1
addE(i, i-1, -1);
}
spfa();
printf("%d\n", dis[maxr]);
}
return 0;
}

------ 本文结束 ------