poj1201

maksyuki 发表于 oj 分类，标签: 图论-差分约束系统

18 3月 2016

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

Source

Southwestern Europe 2002

题目类型：差分约束系统

算法分析：设Si表示集合Z中小于等于i的元素个数，则可由输入得到差分方程组Sai-1 - Sbi <= -Ci。Si还满足0 <= Si - Si-1 <= 1，则可得到方程组Si - Si-1 <= 1和Si-1 - Si <= 0，最后建图跑一个spfa即可

/*************************************************
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;
}

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

超客的水墨烟雨

poj1201

分类目录

标签云

书签

近期评论

2025年4月
一	二	三	四	五	六	日
« 6月
	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