Intervals
You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.
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
The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.
Output
The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.
Sample Input
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
Sample Output
6
Source
题目类型：差分约束系统
算法分析：设Si表示集合Z中小于等于i的元素个数，则可由输入得到差分方程组Sai-1 - Sbi <= -Ci。Si还满足0 <= Si - Si-1 <= 1，则可得到方程组Si - Si-1 <= 1和Si-1 - Si <= 0，最后建图跑一个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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 |
/************************************************* Author :supermaker Created Time :2016/3/18 20:41:31 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 50000 + 6666; struct Node { int v, w, nxt; }; Node edge[maxn*4]; int head[maxn], edgelen; void Init () { memset (edge, -1, sizeof (edge)); memset (head, -1, sizeof (head)); edgelen = 0; } void AddEdge (int u, int v, int w) { edge[edgelen].v = v, edge[edgelen].w = w; edge[edgelen].nxt = head[u]; head[u] = edgelen++; } int dis[maxn], inq[maxn], low, up; void spfa (int s) { for (int i = low; i <= up; i++) { dis[i] = INF; inq[i] = 0; } dis[s] = 0; queue <int> qu; qu.push (s); inq[s]++; while (!qu.empty ()) { int tt = qu.front (); qu.pop (); inq[tt]--; int pa = head[tt]; while (pa != -1) { int pb = edge[pa].v; if (dis[tt] < INF && dis[pb] > dis[tt] + edge[pa].w) { dis[pb] = dis[tt] + edge[pa].w; if (!inq[pb]) { qu.push (pb); inq[pb]++; } } pa = edge[pa].nxt; } } } int main() { //CFF; //CPPFF; int n; while (scanf ("%d", &n) != EOF) { Init (); low = INF, up = -INF; for (int i = 1; i <= n; i++) { int u, v, w; scanf ("%d%d%d", &u, &v, &w); AddEdge (v, u - 1, -w); low = min (low, u - 1); up = max (up, v); } for (int i = low; i <= up; i++) { AddEdge (i, i + 1, 1); AddEdge (i + 1, i, 0); } spfa (up); printf ("%d\n", dis[up] - dis[low]); } return 0; } |
- « 上一篇：zoj2770
- poj1364：下一篇 »