好歹用了一天，也算是看懂了差分约束的原理，做出第一条查分约束了。
题意是告诉你一些区间中最少有多少元素，最少需要多少个元素才能满足所有要求。
构图的方法是，(a)->(b+1)=c。还有就是所有的相邻的点都要连上(i+1)->(i)=0，(i)->(i+1)=-1。因为我对点离散了，所以就变成(rx[i])->(rx[i+1])=rx[i]-rx[i+1]。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream> using namespace std; const int N = ;
const int INF = 0x55555555;
struct Edge {
int id, nx, val;
Edge() {}
Edge(int id, int nx, int val) : id(id), nx(nx), val(val) {}
} edge[N << ];
int eh[N], ec; void init() {
ec = ;
memset(eh, -, sizeof(eh));
} void addedge(int u, int v, int w) {
edge[ec] = Edge(v, eh[u], w);
eh[u] = ec++;
} int rx[N << ], dis[N];
bool vis[N];
queue<int> Q; void spfa(int s) {
while (!Q.empty()) Q.pop();
memset(vis, , sizeof(vis));
for (int i = ; i < N; i++) dis[i] = -INF;
Q.push(s);
vis[s] = true;
dis[s] = ;
while (!Q.empty()) {
int cur = Q.front();
Q.pop();
vis[cur] = false;
for (int t = eh[cur]; ~t; t = edge[t].nx) {
if (dis[edge[t].id] < dis[cur] + edge[t].val) {
dis[edge[t].id] = dis[cur] + edge[t].val;
if (vis[edge[t].id]) continue;
Q.push(edge[t].id);
vis[edge[t].id] = true;
}
}
}
} int main() {
// freopen("in", "r", stdin);
int n, x, y, z;
while (~scanf("%d", &n)) {
init();
int cnt = ;
for (int i = ; i < n; i++) {
scanf("%d%d%d", &x, &y, &z);
addedge(x, y + , z);
rx[cnt++] = x;
rx[cnt++] = y + ;
}
sort(rx, rx + cnt);
cnt = unique(rx, rx + cnt) - rx;
for (int i = ; i < cnt; i++) addedge(rx[i], rx[i - ], rx[i - ] - rx[i]), addedge(rx[i - ], rx[i], );
spfa(rx[]);
printf("%d\n", dis[rx[cnt - ]]);
}
return ;
}
跑的比较慢，元素进队的次数比较多。用固定大小的queue因为越界WA了好多次。
——written by Lyon