查看原题请戳这里
差分约束
差分约束系统：由N个变量$X_1, X_2, X_3 …. X_N$和$M$个未知条件组成的N元一次不等式组，其中，每个条件都形如
$X_i \le X_j + C_k$
我们的问题是：给出一组满足所有条件的解，否则判断出无解
注意到，$X_i\le X_j + c_k$ 与单源最短路中的三角不等式很相似，建立N个节点对应N个变量。对于每组条件，从 j 向i连一条边。同时虚构0号节点并向每一个节点连一条边，如果存在负环则无解。否则有解。
问题转化
那么，我们怎么根据这个题目建立起一个差分约束系统呢？
我们可以用$siz[i]$表示区间$[0,i]$中被选的元素的个数，那么区间$[a_i,b_i]$中被选中的元素的个数我们就可以用$siz[b_i]-siz[a_i-1]$来表示。于是我们就可以从$a_i-1$向$b_i$连一条权值为$w$的有向边。
另外，为了保证图的连通性，我们需要再从每一个数$a$向$a+1$连一条权为$0$的边，从每一个数$a$向$a-1$连一条权为$-1$的边。
那么，为什么这么连呢？
因为$siz[a+1] -siz[a] \le 1$且$siz[a]-siz[a+1]\ge-1$。
最终的图是这个样子的（以该数据为例）![1564974953405]()
![1564974989829]()
code：
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register
using namespace std;
int read()
{
register int x = 0,f = 1;register char ch;
ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
return x * f;
}
int x,y,z,n,cnt,ans,minn,maxx;
int d[200005],vis[200005],dis[200005];
struct edge{
int to,next,v;
}e[200005];
void add(int x,int y,int z)
{
e[++cnt].to = y;
e[cnt].v = z;
e[cnt].next = d[x];
d[x] = cnt;
}
void clannad()
{
for(int i = 0; i <= cnt; i++) e[i].to = 0,e[i].next = 0,e[i].v = 0;
for(int i = 0; i <= cnt; i++) d[i] = 0;
cnt = 0;
}
queue<int> que;
int spfa(int s)
{
while(!que.empty()) que.pop();
for(int i = minn; i <= maxx; i++) dis[i] = -INF;
dis[s] = 0;
memset(vis,0,sizeof(vis));
que.push(s);
dis[s] = 0;
vis[s] = 1;
while(!que.empty())
{
int u = que.front();
que.pop();
vis[u] = 0;
for(int i = d[u]; i; i = e[i].next)
{
int v = e[i].to;
int w = e[i].v;
if(dis[v] < dis[u] + w)
{
dis[v] = dis[u] + w;
if(!vis[v]) que.push(v),vis[v] = 1;
}
}
}
return dis[maxx];
}
int main()
{
int t;
t = read();
for(t; t > 0; t--)
{
n = read();
maxx = -INF;
minn = INF;
for(int i = 1; i <= n; i++)
{
x = read();
y = read();
z = read();
add(x - 1,y,z);
maxx = max(y,maxx);
minn = min(x - 1,minn);
}
for(int i = minn; i <= maxx; i++)
{
add(i,i + 1,0);
add(i + 1, i,-1);
}
int ans = spfa(minn);
printf("%d\n",ans);
clannad();
}
return 0;
}
|
