3971: circle

2024-03-08 23:58
文章标签 circle 3971

本文主要是介绍3971: circle,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

时间限制: 1 Sec 内存限制: 512 MB O2
提交: 122 解决: 23
[提交][状态][博客][加入收藏]
题目描述
小w 的男朋友送给小w 一个nn个点mm条边的图,并且刁难小w 要她找出点数最少的正环。
小w 不会做,于是向你求助。
输入
第一行两个整数n,mn,m。
接下来mm行,每行四个数u,v,a,bu,v,a,b,表示从uu走到vv的代价为aa,从vv走到uu的代价为bb(算作两条不同的边)。注意a,ba,b可能为负。
输出
当图中包含正环时,输出点数最少的正环(简单环)的点数。
否则输出0。
样例输入
3 3
1 2 2 -1
2 3 10 -10
3 1 10 -10
样例输出
2
提示
对于前20%20%的数据,n≤7,m≤10n≤7,m≤10。
对于前60%60%的数据,n≤150,m≤2000n≤150,m≤2000。
对于100%100%的数据,1≤n≤300,0≤m≤n(n−1)2,|a|,|b|≤1041≤n≤300,0≤m≤n(n−1)2,|a|,|b|≤104。
数据保证不存在重边和自环。
来源
2018年10月hnsdfz集训

题解
题目要求的是“在长度为正的条件下点数最少”,而“长度为正”这个条件不好维护,故考虑转化为“点数在一个值之内的最大长度“(为什么不是刚好这个值?请见下文),这样只要找到满足长度为正的最小点数即可。
考虑计算每个点数之内的最大长度,可转化为最长路问题:由于要找的是环,故记F[i][j][k]为i个点之内,从j到k的最长路,对于每一个i,只要有任意f[i][j][j]为正,则可行。从i-1个点数之内向i个点数之内转移,每次跑一遍Floyed,效率为n的四次方。
只要将一个n优化为log即可,而可能优化的只有第一维,那最合适的应该是倍增了。将i改为2的i次方,转移显然。考虑如何统计答案,参照倍增LCA的思想,初始的矩阵为走0步,i从大到小枚举,若走完2的i次方步可行则不走,否则就走,到最后再走一步即可。因为若2的i次方可行,则更大的一定可行,即满足单调性,所以可以这样做(倍增LCA也是由于这样的单调性才可行)。 因此,对于状态F的设计,不应当是恰好i个点(因为不具有单调性),而是i个点之内。
总结:此题的关键在于对题目条件的转化。即将条件——>最值转化为以最值为条件(刚好为该值或以该值为界要具体看题目的需要)——>条件的最值,这样问题就变得可解多了。

这篇关于3971: circle的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/788853

相关文章

【HDU】5343 MZL's Circle Zhou【后缀自动机】

传送门:【HDU】5343 MZL’s Circle Zhou 对于a串可能和b串重复的部分,我们总能找到一个位置,使得a串达到最长,即a串的后继为空,所以我们只要预处理以字符x为开头的b串的个数即可。 my  code: my~~code: #include <bits/stdc++.h>using namespace std ;typedef long long LL ;#defin

[论文笔记]Circle Loss: A Unified Perspective of Pair Similarity Optimization

引言 为了理解CoSENT的loss,今天来读一下Circle Loss: A Unified Perspective of Pair Similarity Optimization。 为了简单,下文中以翻译的口吻记录,比如替换"作者"为"我们"。 这篇论文从对深度特征学习的成对相似度优化角度出发,旨在最大化同类之间的相似度 s p s_p s

poj 3971 Scales (dp)

题目大意: 给你一个重量为w的物品 和 重量分别为 1  2  4  ... 2^(n-1) 的砝码,问 一共有多少种方式使得天平平衡。 解题思路: 让我们求的 就是 w + x = y 并且 x 与 y 在二进制形式下没有相同位置为 1  即  x & y = 0   一开始,我希望用数学公式推出来,但是失败了。后来查看了别人的题解,发现这是一道 动态规划。 我们设 dp[i][j]

使用cv2控制鼠标实现circle的拖拽

2.代码 import numpy as npimport cv2x_center = [100,200,300,400]y_center = [200,200,200,200]radius = 30def mouse_LButtonDown(event, x, y, flags, param):global tempif event == cv2.EVENT_LBUTTONDOW

uvalive 3971 - Assemble(二分搜索 + 贪心)

题目连接:3971 - Assemble 题目大意:有若干个零件, 每个零件给出的信息有种类, 名称, 价格, 质量,  现在给出一个金额, 要求在这个金额范围内, 将每个种类零件都买一个, 并且尽量让这些零件中质量最小的越大, 输出质量最小的值。 解题思路:首先可以用二分搜索确定质量, 然后在搜索的过程中要判断这个质量是否能被满足, 判断函数可以用贪心, 在每一类的零件中选择价格

uva 438 - The Circumference of the Circle(几何)

题目链接:uva 438 - The Circumference of the Circle #include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const double pi = 4 * atan(1);const double eps = 1e

hdu 1374 The Circumference of the Circle

......................................................................................................................................................................... 求圆心公式: x0 = ((y

POJ 1329 Circle Through Three Points

链接:http://poj.org/problem?id=1329 题目: Circle Through Three Points Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 3176 Accepted: 1347 Description Your team is to write a progra

Stability AI 推出稳定音频 2.0:为创作者提供先进的 AI 生成音频 - Circle 阅读助手

概述 Stability AI 的发布再次突破了创新的界限。这一尖端模型以其前身的成功为基础,引入了一系列突破性的功能,有望彻底改变艺术家和音乐家创建和操作音频内容的方式。 Stable Audio 2.0 代表了人工智能生成音频发展的一个重要里程碑,为质量、多功能性和创意潜力设定了新标准。该模型能够生成完整长度的曲目、使用自然语言提示转换音频样本以及产生各种音效,为各行业的内容创作者开辟

突破编程_前端_SVG(circle 圆形)

1 circle 元素的基本属性和用法 SVG 的 <circle> 元素用于在SVG文档中绘制圆形。它具有几个基本属性,允许定义圆形的大小、位置、填充颜色和边框样式。以下是 <circle> 元素的基本属性及其详细解释: 1.1 cx 和 cy 描述:这两个属性定义了圆形的中心点。cx 是圆形中心的 x 坐标,cy 是圆形中心的 y 坐标。示例: <svg width="100" hei