[POJ 1201] Intervals【差分约束系统】
Problem:
Time Limit: 2000MS | Memory Limit: 65536K |
Description
Write a program that:
reads the number of intervals, their end points and integers c1, ..., cn from the standard input,
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n,
writes the answer to the standard output.
Input
Output
Sample Input
5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1
Sample Output
6
Source
Solution:
这题是差分约束系统的经典题。
我们用 S[i] 表示前缀和,即 [1, i] 中有几个整数属于 Z 集合。
于是读入的数据“在 [a, b] 中至少有 c 个整数属于 Z 集合”可以转化为
- S[b] - S[a - 1] ≥ c,可以化为三角不等式如下:
- S[b] ≥ S[a - 1] + c …… i)
而根据题目的隐含条件,每个整数要么不在集合 Z 中,要么只在集合中出现一次,即
- 0 ≤ S[i + 1] - S[i] ≤ 1,可以化为三角不等式如下:
- S[i + 1] ≥ S[i] …… ii)
- S[i] ≥ S[i + 1] - 1 …… iii)
联立 i), ii), iii) 得到差分约束系统。
【差分约束系统的最短/长路求解】
我们可以发现,最短/长路的求解算法的核心松弛操作 (Relax) 就是建立在三角不等式的基础上。所以我们可以通过最短/长路来求解差分约束系统的最值。
求最小值,则将不等式化为 x ≥ y + C 的形式,从 y -> x 连权值为 C 的边,跑最长路即可。
求最大值,则将不等式化为 x ≤ y + C 的形式,从 y -> x 连权值为 C 的边,跑最短路即可。
Code: O(kN) [2476K, 235MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<queue> using namespace std; int n, L = 0x3f3f3f3f, R = 0; struct Edge{ int np, val; Edge *nxt; }; struct Graph{ Edge *V[50005], E[150005]; int tope; inline void addedge(int u, int v, int w){ E[++tope].np = v + 1, E[tope].val = w; E[tope].nxt = V[u + 1], V[u + 1] = &E[tope]; } // Shift subscriptions rightwards to avoid overflowing } G; queue<int> q; bool inq[50005]; int dis[50005]; inline void SPFA_Longest_Path(int S){ memset(dis, -1, sizeof(dis)), dis[S] = 0; q.push(S), inq[S] = 1; while(!q.empty()){ int u = q.front(); q.pop(), inq[u] = 0; for(register Edge *ne = G.V[u]; ne; ne = ne->nxt) if(dis[u] + ne->val > dis[ne->np]){ // Find the longest path dis[ne->np] = dis[u] + ne->val; if(!inq[ne->np]) q.push(ne->np), inq[ne->np] = 1; } } } int main(){ scanf("%d", &n); for(register int i = 1; i <= n; i++){ int a, b, c; scanf("%d%d%d", &a, &b, &c); G.addedge(a - 1, b, c); // S[b] - S[a - 1] >= c ==> S[b] >= S[a - 1] + c L = min(L, a - 1), R = max(R, b); } for(register int i = L; i < R; i++) G.addedge(i, i + 1, 0), G.addedge(i + 1, i, -1); // 0 <= S[i + 1] - S[i] <= 1 ==> S[i + 1] >= S[i] && S[i] >= S[i + 1] - 1 L++, R++; // Shift subscriptions rightwards to avoid overflowing SPFA_Longest_Path(L); printf("%d\n", dis[R]); // dis[] is exactly the S[] which stands for the prefix sum of the numbers in Z return 0; }
发表评论