POJ1201 Intervals（差分约束系统）

红太狼 2021-11-17 13:54 295阅读 0赞

## 题意：有n个如下形式的条件:ai bi ci，表示在区间\[ai, bi\]内至少要选择ci个整数点。问你满足n个条件的情况下,最少需要选多少个点? ##

## 分析：差分约束板子题，详见《算法竞赛进阶指南》P394。 ##

## 代码： ##

#include <queue>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int N = 500006, M = 5000006;
    int n, m, d[N];
    int Head[N], Edge[M], Leng[M], Next[M], tot;
    bool v[N];
    
    inline void add(int x, int y, int z) {
    	Edge[++tot] = y;
    	Leng[tot] = z;
    	Next[tot] = Head[x];
    	Head[x] = tot;
    }
    
    void spfa() {
    	queue<int> q;
    	q.push(0);
    	v[0] = 1;
    	d[0] = 0;
    	while (q.size()) {
    		int x = q.front();
    		q.pop();
    		v[x] = 0;
    		for (int i = Head[x]; i; i = Next[i]) {
    			int y = Edge[i];
    			if (d[y] < d[x] + Leng[i]) {
    				d[y] = d[x] + Leng[i];
    				if (!v[y]) {
    					v[y] = 1;
    					q.push(y);
    				}
    			}
    		}
    	}
    }
    
    int main() {
    	memset(d, 0xcf, sizeof(d));
    	tot = m = 0;
    	cin >> n;
    	for (int i = 1; i <= n; i++) {
    		int x, y, z;
    		scanf("%d %d %d", &x, &y, &z);
    		add(x, y + 1, z);
    		m = max(m, y + 1);
    	}
    	for (int i = 1; i <= m; i++) {
    		add(i - 1, i, 0);
    		add(i, i - 1, -1);
    	}
    	spfa();
    	cout << d[m] << endl;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，295人围观）

还没有评论，来说两句吧...

相关阅读

相关差分约束系统详解

一直不知道差分约束是什么类型题目，最近在写最短路问题就顺带看了下，原来就是给出一些形如x-y<=b不等式的约束，问你是否满足有解的问题好神奇的是这类问题竟然可以转换成图论里

男娘i/ 2022年09月27日 06:29/ 0 赞/ 178 阅读

相关 POJ 3169-Layout（差分约束系统-入门裸题）

Layout <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

梦里梦外;/ 2022年09月25日 05:12/ 0 赞/ 102 阅读

相关 POJ 1364-King（差分约束系统）

King <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

女爷i/ 2022年09月25日 04:18/ 0 赞/ 169 阅读

相关 HDU 1384(差分约束系统)

题目要求的是求的最短路，则对于不等式 f(b)-f(a)>=c,建立一条 a 到 b 的边权值为 c(因为当前点b由源点a与值c来判断),则求的最长路即为最小

我不是女神ヾ/ 2022年09月20日 12:48/ 0 赞/ 156 阅读

相关差分约束系统C++实现

差分约束：线性规划矩阵A的每一行包含一个1与一个-1，其他元素为0.因此，由Ax<=b给出的约束条件是m个差分约束集合，其中包含n个未知元。每个约束条件为不等式： xj-x

怼烎@/ 2022年06月18日 12:43/ 0 赞/ 200 阅读

相关 POJ 3159-Candies（差分约束系统-SPFA+邻接表）

Candies <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1500MS</td>

逃离我推掉我的手/ 2022年06月17日 12:50/ 0 赞/ 184 阅读

相关差分约束系统C++实现

差分约束：线性规划矩阵A的每一行包含一个1与一个-1，其他元素为0.因此，由Ax<=b给出的约束条件是m个差分约束集合，其中包含n个未知元。每个约束条件为不等式： xj-x

雨点打透心脏的1/2处/ 2022年05月15日 13:22/ 0 赞/ 228 阅读

相关 Layout POJ - 3169 (差分约束+最短路)

Like everyone else, cows like to stand close to their friends when queuing for feed. FJ

墨蓝/ 2022年04月23日 23:36/ 0 赞/ 183 阅读

相关 POJ1201 Intervals（差分约束系统）

题意：有n个如下形式的条件:ai bi ci，表示在区间\[ai, bi\]内至少要选择ci个整数点。问你满足n个条件的情况下,最少需要选多少个点? 分析：差分约束板子

红太狼/ 2021年11月17日 13:54/ 0 赞/ 296 阅读

相关差分约束系统

差分约束系统前言:在清北学堂模拟赛的差分约束题写炸了，感觉有必要来总结一下差分约束问题模型 -------------------- 求解由若干不等式限制的

偏执的太偏执、/ 2021年10月29日 13:34/ 0 赞/ 396 阅读