ZOJ-1508|ZOJ-1508 Intervals 差分约束 ZOJ-1508Intervals差分约束

题意：给定若干个连续的整数区间[ai, bi]以及ci，现在要求这样一个集合Z，集合Z中的元素与每个给定的区间的元素交集至少有ci个。
解法：通过把dis[i]看做Z中小于等于整数i一共有多少个元素。那么对于题目给定条件有表达式dis[b] - dis[a-1] >= ci，根据这个不等式就能够进行构边了。除此之外，还有一些隐含的条件：0 <= dis[i]-dis[i-1] <= 1，对这些关系同样进行构边。然后要求的值就是dis[Max] - dis[Min-1] >= M中的M，其中Max和Min是出现的最小左、右边界，令dis[Max] = 0，那么就是求解的就是从Max到Min-1的最短路的相反数。

文章图片

这里解释下为什么是从Max到Min-1的最短路，由于有dis[Max]-dis[Min-1]>=M恒成立时，而M同样是一个变量，因此要大于M就要大于M的最大值，因此问题转化为这个不等式中如何求解M的最大值，通过对式子的转化就为dis[Min-1]-dis[Max]<=-M，也就是求-M的最小值，而这个-M在途中最小就是Min-1到Max的最短路了，否则dis[Min-1]就会被dis[Max]-M代替了。
代码如下：

#include #include #include #include #include using namespace std; int N, idx, head[50005]; int Min, Max; // 设对图求出最短路表示的信息dis[i]表示Z集合中包含有多少个小于i的数 struct Edge { int v, ct, next; }e[160000]; void insert(int a, int b, int ct) { e[idx].v = b, e[idx].ct = ct; e[idx].next = head[a]; head[a] = idx++; }int dis[50005]; char vis[50005]; #include void spfa() { queueq; memset(dis, 0x3f, sizeof (dis)); memset(vis, 0, sizeof (vis)); q.push(Max); vis[Max] = 1, dis[Max] = 0; while (!q.empty()) { int v = q.front(); q.pop(); vis[v] = 0; int tv; for (int i = head[v]; i != -1; i = e[i].next) { if (dis[e[i].v] > dis[v] + e[i].ct) { dis[e[i].v] = dis[v] + e[i].ct; if (!vis[e[i].v]) { q.push(e[i].v); vis[e[i].v] = 1; } } } } }int main() { int a, b, c; while (scanf("%d", &N) != EOF) { idx = 0; Min = 50005, Max = 0; memset(head, 0xff, sizeof (head)); for (int i = 0; i < N; ++i) { scanf("%d %d %d", &a, &b, &c); ++a, ++b; // 由于0是有效的数字，因此待会最小数减1将会出现负数 Min = min(Min, a); Max = max(Max, b); insert(b, a-1, -c); } for (int i = Min; i <= Max; ++i) { insert(i-1, i, 1); insert(i, i-1, 0); } spfa(); printf("%d\n", -dis[Min-1]); } return 0; }

【ZOJ-1508|ZOJ-1508 Intervals 差分约束】转载于:https://www.cnblogs.com/Lyush/archive/2013/03/13/2957731.html