HDU 1384(差分约束系统)

2024-09-01 04:58
文章标签 系统 差分 hdu 约束 1384

本文主要是介绍HDU 1384(差分约束系统)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目要求的是求的最短路，
则对于 不等式  f(b)-f(a)>=c,建立 一条 a 到 b 的边 权值为 c(因为当前点b由源点a与值c来判断),则求的最长路 即为 最小值(集合)
并且有隐含条件：0<=f(a)-f(a-1)<=1  则有边权关系(a,a-1,0)以及(a-1,a,-1);
将源点到各点的距离初始化为INF(无穷大)，其中之1为0，最终求出的最短路满足 它们与该点之间相互差值最大
差分约束
　在实际的应用中，一般使用SPFA(Shortest Path Fast Algorithm)算法来实现。
　　差分约束系统中源点到每个点的距离确定
　　关于Dist[]的初始化化
　　1.如果将源点到各点的距离初始化为0，最终求出的最短路满足 它们之间相互最接近了
　　2.如果将源点到各点的距离初始化为INF(无穷大)，其中之1为0，最终求出的最短路满足 它们与该点之间相互差值最大。
　　3.差分约束系统的确立要根据自己确定的约束条件，从约束点走向被约束点
　　连边一般有两种方法，第一种是连边后求最长路的方法，第二种是连边后求最短路的方法。
　　例：d[x]-d[y]>=Z
　　如果想连边后求最长路 那么将不等式变形为这种形式 d[x]>=d[y]+z y---x连一条权值为z的边
　　求最短路则变形成d[y]<=d[x]-z x---y连一条权值为-z的边。
　　如果是别的不等式，也可以根据情况变形。但是要保证的是 两个变量（x,y)的系数一定要是正的。而常量则不一定。
第一：
感觉难点在于建图
第二：
①：对于差分不等式，a - b <= c ，建一条 b 到 a 的权值为 c 的边，求的是最短路，得到的是最大值
②：对于不等式 a - b >= c ，建一条 b 到 a 的权值为 c 的边，求的是最长路，得到的是最小值
③：存在负环的话是无解
④：求不出最短路（dist[ ]没有得到更新）的话是任意解
第三：
一种建图方法：
设x[i]是第i位置（或时刻）的值（跟所求值的属性一样），那么把x[i]看成数列，前n项和为s[n]，则x[i] = s[i] - s[i-1]；
那么这样就可以最起码建立起类似这样的一个关系：0 <= s[i] - s[i-1] <= 1;
其他关系就要去题目探索了

题目意思就是:  给出一系列三元组 R ( x, y, v ) , 表示在闭区间 [x,y] 中有 v 个不同的整数出现,

现在要你求一个最小的集合, 使得集合中的元素满足所有的元组, 且集合元素最少.

定义函数 S( x ) , 表示[0,x] 中出现元素的个数, 那么对于元组 R ( x, y, v )  有 S( y ) – S( x-1 ) >= v.

因为这样的元组又很多, 所以就构成了一组约束序列, 也就是差分约束了 ( 大概是因为它们的差值S( y ) – S( x-1 ) >= v.满足一些约束 ) .

我们看看 SPFA 的一个松弛操作 : if ( R[y] > R[x] + v[y] ) R[y] = R[x] + v[y]; 可以发现, 它是在新增条件

比原定条件更优时, 对原定条件进行优化( 也就是松弛 ) .  这样进行了一系列的松弛以后, 结果就是

最优的了( 详细可以看SPFA的证明 ).  对比一个元组的关系 S( y ) – S( x-1 ) >= v,  以及最终关系 :

S( MAX ) – S ( MIN )  >= RES,  (其中 MAX 为序列中的出现的最大值, MIN 为最小值).   那么必然存在一个

一个min ( RES ),  使得最终关系成立,  怎样求这个最小值呢?    看到前面的SPFA的松弛操作就应该明白

了, 这也是一步步对结果进行松弛的过程, 直到不能松弛.

另外, 仅仅使用题给的元组进行构图, 那么这个图不是强连通的, S 存在隐藏关系 :

S(i+1) – S (i) >= 0 

S ( i ) – S ( i+1 ) >= -1

加上这2个关系整个图就是强连通的了.

 

add（a, b+1, c）由a指向b+1，权值为c。。a走到b+1要加上值c。

按最小值最长路：

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <climits>
using namespace std;
#define maxn 50010
#define maxedges maxn*3
struct edge
{
int v, w, next;
} edges[maxedges];
int head[maxn], cnt;
void add(int u, int v, int w)
{
edges[cnt].v = v;
edges[cnt].w = w;
edges[cnt].next = head[u];
head[u] = cnt++;
}
int SPFA(int start, int target)
{
queue<int> q;
bool inque[maxn];
int d[maxn];
for (int i = 0; i < maxn; ++i) d[i] = -maxn;
memset(inque, false, sizeof inque);
d[start] = 0;
q.push(start);
while (!q.empty())
{
int u = q.front(); q.pop();
inque[u] = false;
for (int e = head[u]; e != -1; e = edges[e].next)
if (d[edges[e].v] < d[u] + edges[e].w)
{
d[edges[e].v] = d[u] + edges[e].w;
if (!inque[edges[e].v])
{
inque[edges[e].v] = true;
q.push(edges[e].v);
}
}
}
return d[target];
}
int main()
{
int n, a, b, c, i, _min, _max;
while (cin >> n)
{
_min = maxn, _max = 0;
memset(head, -1, sizeof head);
cnt = 0;
for (i = 0; i < n; ++i)
{
cin >> a >> b >> c;
add(a, b + 1, c);
_min = _min > a ? a : _min;
_max = _max < b + 1 ? b + 1 : _max;
}
for (i = _min + 1; i <= _max; ++i)
{
add(i - 1, i, 0);
add(i, i - 1, -1);
}
printf("%d\n", SPFA(_min, _max));
}
}


按最短路最大值：

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <climits>
using namespace std;
#define maxn 50010
#define maxedges maxn*3
struct edge
{
int v, w, next;
} edges[maxedges];
int head[maxn], cnt;
void add(int u, int v, int w)
{
edges[cnt].v = v;
edges[cnt].w = w;
edges[cnt].next = head[u];
head[u] = cnt++;
}
int SPFA(int start, int target)
{
queue<int> q;
bool inque[maxn];
int d[maxn];
for (int i = 0; i < maxn; ++i) d[i] = maxn;
memset(inque, false, sizeof inque);
d[start] = 0;
q.push(start);
while (!q.empty())
{
int u = q.front(); q.pop();
inque[u] = false;
for (int e = head[u]; e != -1; e = edges[e].next)
if (d[edges[e].v] > d[u] + edges[e].w)
{
d[edges[e].v] = d[u] + edges[e].w;
if (!inque[edges[e].v])
{
inque[edges[e].v] = true;
q.push(edges[e].v);
}
}
}
return d[target];
}
int main()
{
int n, a, b, c, i, _min, _max;
while (scanf("%d", &n) != EOF)
{
_min = maxn, _max = 0;
memset(head, -1, sizeof head);
cnt = 0;
for (i = 0; i < n; ++i)
{
cin >> a >> b >> c;
add(b + 1, a, -c);
_min = _min > a ? a : _min;
_max = _max < b + 1 ? b + 1 : _max;
}
for (i = _min + 1; i <= _max; ++i)
{
add(i - 1, i, 1);
add(i, i - 1, 0);
}
printf("%d\n", -SPFA(_max, _min)); //SPFA(_min, _max)
}
}


最小值最长路，add（a，b+1，c）换成add（b+1，a，c），由大走向小。：

对比上面与最小值最长路、最大值最短路的差别：

 

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <climits>
using namespace std;
#define maxn 50010
#define maxedges maxn*3
struct edge
{
int v, w, next;
} edges[maxedges];
int head[maxn], cnt;
void add(int u, int v, int w)
{
edges[cnt].v = v;
edges[cnt].w = w;
edges[cnt].next = head[u];
head[u] = cnt++;
}
int SPFA(int start, int target)
{
queue<int> q;
bool inque[maxn];
int d[maxn];
for (int i = 0; i < maxn; ++i) d[i] = -maxn;
memset(inque, false, sizeof inque);
d[start] = 0;
q.push(start);
while (!q.empty())
{
int u = q.front(); q.pop();
inque[u] = false;
for (int e = head[u]; e != -1; e = edges[e].next)
if (d[edges[e].v] < d[u] + edges[e].w)
{
d[edges[e].v] = d[u] + edges[e].w;
if (!inque[edges[e].v])
{
inque[edges[e].v] = true;
q.push(edges[e].v);
}
}
}
return d[target];
}
int main()
{
int n, a, b, c, i, _min, _max;
while (scanf("%d", &n) != EOF)
{
_min = maxn, _max = 0;
memset(head, -1, sizeof head);
cnt = 0;
for (i = 0; i < n; ++i)
{
cin >> a >> b >> c;
add(b + 1, a, c);
_min = _min > a ? a : _min;
_max = _max < b + 1 ? b + 1 : _max;
}
for (i = _min + 1; i <= _max; ++i)
{
add(i - 1, i, -1);
add(i, i - 1, 0);
}
printf("%d\n", SPFA(_max, _min)); //SPFA(_min, _max)
}
}


 最各节点进行排序，去重，建边，对比与上面代码的区别：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
const int N = 55555;
const int INF = 0x55555555;
struct Edge {
int id, nx, val;
Edge() {}
Edge(int id, int nx, int val) : id(id), nx(nx), val(val) {}
} edge[N << 2];
int eh[N], ec;
void init() {
ec = 0;
memset(eh, -1, sizeof(eh));
}
void addedge(int u, int v, int w) {
edge[ec] = Edge(v, eh[u], w);
eh[u] = ec++;
}
int rx[N << 1], dis[N];
bool vis[N];
queue<int> Q;
void spfa(int s) {
while (!Q.empty()) Q.pop();
memset(vis, 0, sizeof(vis));
for (int i = 0; i < N; i++) dis[i] = -INF;
Q.push(s);
vis[s] = true;
dis[s] = 0;
while (!Q.empty()) {
int cur = Q.front();
Q.pop();
vis[cur] = false;
for (int t = eh[cur]; ~t; t = edge[t].nx) {
if (dis[edge[t].id] < dis[cur] + edge[t].val) {
dis[edge[t].id] = dis[cur] + edge[t].val;
if (vis[edge[t].id]) continue;
Q.push(edge[t].id);
vis[edge[t].id] = true;
}
}
}
}
int main() {
//    freopen("in", "r", stdin);
int n, x, y, z;
while (~scanf("%d", &n)) {
init();
int cnt = 0;
for (int i = 0; i < n; i++) {
scanf("%d%d%d", &x, &y, &z);
addedge(x, y + 1, z);
rx[cnt++] = x;
rx[cnt++] = y + 1;
}
sort(rx, rx + cnt);
cnt = unique(rx, rx + cnt) - rx;
for (int i = 1; i < cnt; i++) addedge(rx[i], rx[i - 1], rx[i - 1] - rx[i]), addedge(rx[i - 1], rx[i], 0);
spfa(rx[0]);
printf("%d\n", dis[rx[cnt - 1]]);
}
return 0;
}


 

这篇关于HDU 1384(差分约束系统)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1126006。

相关文章

SQL中的外键约束

SQL中的外键约束

外键约束用于表示两张表中的指标连接关系。外键约束的作用主要有以下三点： 1.确保子表中的某个字段（外键）只能引用父表中的有效记录2.主表中的列被删除时，子表中的关联列也会被删除3.主表中的列更新时，子表中的关联元素也会被更新 子表中的元素指向主表 以下是一个外键约束的实例展示
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
基于人工智能的图像分类系统

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务，目标是自动识别图像中的对象类别。通过卷积神经网络（CNN）等深度学习技术，我们可以构建高效的图像分类系统，广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统，包括环境
阅读更多...
水位雨量在线监测系统概述及应用介绍

水位雨量在线监测系统概述及应用介绍

在当今社会，随着科技的飞速发展，各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中，水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术，其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成，形成了一个完整的闭环系统。 数据采集单元：这是系统的“眼睛”，
阅读更多...
嵌入式QT开发：构建高效智能的嵌入式系统

嵌入式QT开发：构建高效智能的嵌入式系统

摘要： 本文深入探讨了嵌入式 QT 相关的各个方面。从 QT 框架的基础架构和核心概念出发，详细阐述了其在嵌入式环境中的优势与特点。文中分析了嵌入式 QT 的开发环境搭建过程，包括交叉编译工具链的配置等关键步骤。进一步探讨了嵌入式 QT 的界面设计与开发，涵盖了从基本控件的使用到复杂界面布局的构建。同时也深入研究了信号与槽机制在嵌入式系统中的应用，以及嵌入式 QT 与硬件设备的交互，包括输入输出设
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
hdu 2093 考试排名（sscanf）

hdu 2093 考试排名（sscanf）

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()"，有时候又没有。而它也不会给我们提示。 这种情况下，就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和
阅读更多...
hdu 2602 and poj 3624(01背包)

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码： #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2