首页 > 其他分享 >负环的习题和应用

负环的习题和应用

时间：2024-06-09 23:22:05浏览次数：20  
标签：cur int double mid 负环 vis 应用 习题 dis

\(\text{update 2024/6/9: }\) 文中提到了速度较快的 \(\text{DFS-SPFA}\)，虽然速度较好，但是容易被卡，例如模板！

大家好，我是Weekoder！

今天要讲的是负环的一些习题与负环在题目中的应用。

一共有 \(3\) 个例题，分别为：

\(\color{#52C41A}\texttt{P2136}\)，\(\color{#9D3DCF}\texttt{P2868}\)，\(\color{#9D3DCF}\texttt{P3199}\)。（点击有 \(\text{Link}\)）

\(\color{#52C41A}\texttt{P2136}\) 拉近距离

题面

在小明和小红的生活中，有 \(N\) 个关键的节点。有 \(M\) 个事件，记为一个三元组 \((S_i,T_i,W_i)\)，表示从节点 \(S_i\) 有一个事件可以转移到 \(T_i\)，事件的效果就是使他们之间的距离减少 \(W_i\)。

这些节点构成了一个网络，其中节点 \(1\) 和 \(N\) 是特殊的，节点 \(1\) 代表小明，节点 \(N\) 代表小红，其他代表进展的阶段。所有事件可以自由选择是否进行，但每次只能进行当前节点邻接的。请你帮他们写一个程序，计算出他们之间可能的最短距离。如果这个距离可以无限缩小，输出Forever love。

分析

可以把题意理解为一个人在一条路径上不断往另一个人的方向走。

注意到题目中说距离会减少 \(W_i\)，那么边权即为负。正常来说，跑一遍 SPFA 就可以了，答案是 \(dis_n\)。但是注意到不仅是小明可以去找小红，小红也可以去找小明，于是做两遍 SPFA，分别为 \(\text{spfa(1)}\) 和 \(\text{spfa(n)}\)，最后取 \(\min\)。\(\texttt{Forever love}\) 就是判断有没有负环，除此之外和 SPFA 判负环没有区别。由于没有负环要输出最短路，所以考虑使用 BFS-SPFA。

\(\text{Code:}\)

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;

struct Edge {
	int to, w;
};

int n, m, dis[N], dp[N];
bool vis[N];

vector<Edge> nbr[N];

bool spfa(int s) {
	queue<int> q;
	memset(vis, 0, sizeof vis);
	memset(dis, 0x3f, sizeof dis);
	memset(dp, 0, sizeof dp);
	dis[s] = 0;
	vis[s] = 1;
	q.push(s);
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		vis[cur] = 0;
		for (auto nxt : nbr[cur]) {
			int to = nxt.to, w = nxt.w;
			if (dis[to] > dis[cur] + w) {
				dis[to] = dis[cur] + w;
				dp[to] = dp[cur] + 1;
				if (dp[to] >= n) return 1;
				if (!vis[to]) {
					vis[to] = 1;
					q.push(to);
				}
			}
		}
	}
	return 0;
}

int main() {
	cin >> n >> m;
	for (int i = 1, u, v, w; i <= m; i++) {
		cin >> u >> v >> w;
		nbr[u].emplace_back((Edge){v, -w});
	}
	if (spfa(1)) {
	    cout << "Forever love";
	    return 0;
	}
	int tmp = dis[n];
	if (spfa(n)) {
	    cout << "Forever love";
	    return 0;
	}
	cout << min(dis[1], tmp);
	return 0;
}

\(\color{#9D3DCF}\texttt{P2868}\) Sightseeing Cows G

题面

给你一张 \(n\) 点 \(m\) 边的有向图，第 \(i\) 个点点权为 \(F_i\)，第 \(i\) 条边边权为 \(T_i\)。

找一个环，设环上的点组成的集合为 \(S\)，环的边组成的集合为 \(E\)，最大化 \(\dfrac{\sum_{u\in S}F_u}{\sum_{e\in E}T_e}\)。

分析

考虑二分答案。

设二分答案 \(mid\)，因为要找最大值，所以我们设还有一个更大值。这个值就是 \(\dfrac{\sum_{u\in S}F_u}{\sum_{e\in E}T_e}\)，所以假设我们有：\(\dfrac{\sum_{u\in S}F_u}{\sum_{e\in E}T_e}>mid\)。如果成立，就猜大些，否则猜小些。但是这个不好判断，所以我们来推一下式子（在一个环中，点数 \(=\) 边数）：

\[\begin{aligned} {} & \dfrac{\sum_{u\in S}F_u}{\sum_{e\in E}T_e}>mid \\ = & \sum_{u\in S}F_u>mid\cdot \sum_{e\in E}T_e \\ = & mid\cdot \sum_{e\in E}T_e-\sum_{u\in S}F_u<0 \\ = & \sum(mid\cdot T_e-F_u)<0 \end{aligned} \]

推到这里，我们发现了一个有趣的结论：若想继续猜大些，则需要满足对于环上的边权之和，有 \(mid\cdot T_e-F_u<0\)。我们把 \(mid\cdot T_e-F_u\) 看作边权，那这不就变成了一个找负环的问题吗？没错，在简单的计算后，我们得到了一个结论：找负环。

在这里，就仅仅需要判断是否有负环并二分答案，推荐使用 DFS-SPFA，用时仅有 \(46\text{ms}\)。对于 BFS-SPFA，也能过，不过时间为 \(83\text{ms}\)。

\(\text{Code:}\)

\(\text{DFS-SPFA}\)

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;
const double eps = 1e-6;

struct Edge {
    int to;
    double w;
};

int n, m;
double dis[N], f[N];
bool vis[N];

vector<Edge> nbr[N];

bool spfa(int cur, double X) {
    vis[cur] = 1;
    for (auto nxt : nbr[cur]) {
        int to = nxt.to;
        double w = nxt.w * X - f[cur];
        if (dis[to] > dis[cur] + w) {
            dis[to] = dis[cur] + w;
            if (vis[to] || spfa(to, X)) return 1;
        }
    }
    vis[cur] = 0;
    return 0;
}

bool check(double X) {
    memset(vis, 0, sizeof vis);
    memset(dis, 0, sizeof dis);
    for (int i = 1; i <= n; i++)
        if (spfa(i, X))
            return 1;
    return 0;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> f[i];
    double l = 1005, r = -1;
    for (int i = 1, u, v; i <= m; i++) {
        double w;
        cin >> u >> v >> w;
        nbr[u].emplace_back((Edge){v, w});
        l = min(l, w);
        r = max(r, w);
    }
    r++, l--;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    printf("%.2lf", l);
    return 0;
}

\(\text{BFS-SPFA}\)

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;
const double eps = 1e-6;

struct Edge {
	int to;
	double w;
};

int T, n, m, dp[N];
double dis[N], f[N];
bool vis[N];

vector<Edge> nbr[N];

bool spfa(double X) {
	queue<int> q;
	memset(vis, 0, sizeof vis);
	memset(dis, 0, sizeof dis);
	memset(dp, 0, sizeof dp);
	for (int i = 1; i <= n; i++)
		vis[i] = 1, q.push(i);
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		vis[cur] = 0;
		for (auto nxt : nbr[cur]) {
			int to = nxt.to;
			double w = X * nxt.w - f[cur];
			if (dis[to] > dis[cur] + w) {
				dis[to] = dis[cur] + w;
				dp[to] = dp[cur] + 1;
				if (dp[to] >= n) return 1;
				if (!vis[to]) {
					vis[to] = 1;
					q.push(to);
				}
			}
		}
	}
	return 0;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> f[i];
	double l = 1005, r = -1;
	for (int i = 1, u, v; i <= m; i++) {
		double w;
		cin >> u >> v >> w;
		nbr[u].emplace_back((Edge){v, w});
		l = min(l, w);
		r = max(r, w);
	}
	double tmp = r + 1;
	r++, l--;
	while (r - l > eps) {
		double mid = (l + r) / 2;
		if (spfa(mid)) l = mid;
		else r = mid;
	}
	printf("%.2lf", l);
	return 0;
}

\(\color{#9D3DCF}\texttt{P3199}\) 最小圈

题面

考虑带权有向图 \(G=(V,E)\) 以及 \(w:E\rightarrow \mathbb{R}\)，每条边 \(e=(i,j)\)（\(i\neq j\)，\(i, j\in V\)）的权值定义为 \(w_{i,j}\)。设 \(n=|V|\)。

\(c=(c_1,c_2,\cdots,c_k)\)（\(c_i\in V\)）是 \(G\) 中的一个圈当且仅当 \((c_i,c_{i+1})\)（\(1\le i<k\)）和 \((c_k,c_1)\) 都在 \(E\) 中。称 \(k\) 为圈 \(c\) 的长度，同时记 \(c_{k+1}=c_1\)，并定义圈 \(c=(c_1,c_2,\cdots,c_k)\) 的平均值为

\[\mu(c)= \frac 1 k \sum\limits_{i=1}^{k} w_{c_i,c_{i+1}} \]

即 \(c\) 上所有边的权值的平均值。设 \(\mu'(G)=\min_c\mu(c)\) 为 \(G\) 中所有圈 \(c\) 的平均值的最小值。

给定图 \(G=(V,E)\) 以及 \(w:E\rightarrow \mathbb{R}\)，求出 \(G\) 中所有圈 \(c\) 的平均值的最小值 \(\mu'(G)\)。

题面概括

给定一个图，找一个环，最小化

\[\frac 1 k \sum\limits_{i=1}^{k} w_{c_i,c_{i+1}} \]

分析

考虑二分答案。

设二分答案 \(mid\)，这次要找最小值，于是设 \(\frac 1 k \sum\limits_{i=1}^{k} w_{c_i,c_{i+1}}<mid\)。继续推公式：

\[\begin{aligned} & \frac 1 k \sum\limits_{i=1}^{k} w_{c_i,c_{i+1}}<mid \\ = & mid\cdot k>\sum\limits_{i=1}^{k}w_{c_i,c_{i+1}} \\ = & \sum\limits_{i=1}^{k}(mid-w_{c_i,c_{i+1}})>0 \\ = & \sum\limits_{i=1}^{k}(w_{c_i,c_{i+1}}-mid)<0 \\ \end{aligned} \]

于是我们又得到了：将边权看作原边权 \(-mid\)，判负环。

这个题需要用 DFS-SPFA，否则会 \(\color{#052242}\texttt{TLE}\) 挂 \(50\text{pts}\)。

\(\text{Code:}\)

#include <bits/stdc++.h>
using namespace std;

const int N = 3e3 + 5;
const double eps = 1e-9;

struct Edge {
    int to;
    double w;
};

int n, m;
double dis[N];
bool vis[N];

vector<Edge> nbr[N];

bool spfa(int cur, double X) {
    vis[cur] = 1;
    for (auto nxt : nbr[cur]) {
        int to = nxt.to;
        double w = nxt.w - X;
        if (dis[to] > dis[cur] + w) {
            dis[to] = dis[cur] + w;
            if (vis[to] || spfa(to, X)) return 1;
        }
    }
    vis[cur] = 0;
    return 0;
}

bool check(double X) {
    memset(dis, 0, sizeof dis);
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= n; i++)
        if (spfa(i, X)) return 1;
    return 0;
}
int main() {
    cin >> n >> m;
    double l = 1e8, r = -1e8;
    for (int i = 1, u, v; i <= m; i++) {
        double w;
        cin >> u >> v >> w;
        nbr[u].emplace_back((Edge){v, w});
        l = min(l, w);
        r = max(r, w);
    }
    r++, l--;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    printf("%.8lf", r);
    return 0;
}

小结

以上就是关于负环的三个习题的内容。负环是一个判定型的算法，适合搭配二分答案等算法，发挥更大的用处。今天的习题都有一些难度，需要巩固练习。

再见！

标签：cur,int,double,mid,负环,vis,应用,习题,dis
From： https://www.cnblogs.com/Weekoder/p/18240228

相关文章

  • KDY----BFS_宽度优先搜索习题
    题目由可达鸭提供，本篇够  字，阅读时注意休息和暂停。一、课时提交情（AC情况）T1、武士风度的牛  100/100（老师带着做的。）T2、抓住那头牛100/100T3、仙岛求药  100/100T4、TheCastle 0/100（时间不够了，就看了看题目。）二、目录T1、武士风度的牛T2、抓住那头牛T......
  • linux系统安全及应用
    一、账号安全控制用户账号是计算机使用者的身份凭证或标识，每个要访问系统资源的人，必须凭借其用户账号才能进入计算机。在 Linux 系统中，提供了多种机制来确保用户账号的正当、安全使用。1、账号的基本安全措施（1）系统账号清理常见的非登录用户账号包括 bin、daemon、adm、l......
  • 开源模型应用落地-LangSmith试炼-入门初体验-Prompts（六）
    一、前言  在许多应用程序中，特别是在大型语言模型(LLM)应用程序中，收集用户反馈以了解应用程序在实际场景中的表现是非常重要的。  本章是LangSmith系列最后一篇文章，通过学习Prompts功能，用户可以上传、浏览、检索和管理提示（Prompt）。这个Prompts功能简化了提示（Prompt）的......
  • OpenCV与AI深度学习 | 实战 | OpenCV实现扫描文本矫正应用与实现详解(附源码)
    本文来源公众号“OpenCV与AI深度学习”，仅用于学术分享，侵权删，干货满满。原文链接：实战|OpenCV实现扫描文本矫正应用与实现详解(附源码)1导 读    本文主要介绍使用OpenCV对扫描文本矫正的应用实例及详细实现步骤。    2背景介绍  在使用打印机或扫描仪......
  • C++ primer plus习题及解析第八章（函数探幽）
    题目：8.11.编写通常接受一个参数(字符串的地址),并打印该字符串的函数。然而,如果提供了第二个参数(int类型），且该参数不为0，则该函数打印字符串的次数将为该函数被调用的次数(注意,字符串的打印次数不等于第二个参数的值而等于函数被调用的次数)。是的，这是一个非常可笑的函数，但......
  • 实验6 C语言结构体、枚举应用编程
    #defineN3//运行程序输入测试时，可以把这个数组改小一些输入测试#include<stdlib.h>typedefstructstudent{intid;//学号charname[20];//姓名charsubject[20];//考试科目doubleperf;//平时成绩......
  • 【数据结构·队列】链队列（带头结点）模板简单应用算法设计：长整数加法计算
    目的：使用C++模板设计链队列的抽象数据类型（ADT）。并在此基础上，使用链队列ADT的基本操作，设计并实现简单应用的算法设计。内容：（1）请参照单链表的ADT模板，设计链队列的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及......
  • 瑞吉外卖涉及到的应用层
    目录SpringBoot常用的SpringBoot核心注解：SpringBootStarter的工作原理 优点：  小结：Spring 核心特性小结 SpringMVC 核心组件工作流程小结 SpringSession 会话存储的方式小结lombok    lombok主要特性和功能： 小结：Swagger 核心组件 主要特......
  • C++的近邻算法详解及应用
            近邻算法，也被称为最近邻算法或k-近邻算法（k-NN），是一种基本的分类和回归方法。它基于实例进行学习，无需进行模型训练，而是直接通过计算待分类样本与已知类别样本之间的距离来确定其所属类别。在C++中，我们可以通过编写特定的函数或利用现有的库来实现近邻算法。  ......
  • 构建和谐网络环境：AI敏感词屏蔽技术的应用与挑战
    在当今信息爆炸的时代，网络空间的信息安全和言论自由之间的平衡成为了一个重要议题。为了维护网络环境的健康发展，一种能够自动屏蔽敏感词的AI技术应运而生。本文将结合“智谱清言”的智能体“净言”为例，探讨AI敏感词屏蔽技术的应用及其面临的挑战。一、AI敏感词屏蔽技术的原理与应......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99