[USACO07DEC] Sightseeing Cows G(分数规划+负权回路判定)

这篇具有很好参考价值的文章主要介绍了[USACO07DEC] Sightseeing Cows G(分数规划+负权回路判定)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题面

[USACO07DEC] Sightseeing Cows G - 洛谷

题目大意:

给出一张n点m边的带点权带边权的有向图

求一个回路使得路上点权和除以边权和最大(最优比率回路)

题解

首先一定仔细读题,是回路不是路径

由于回路上所有点权只能获取一次,但边权会获取很多次,所以最优解一定是简单回路(无重复边)

然后我们发现是让一个分数最大,于是我们可以考虑分数规划二分

假设二分的商为mid,判断是否存在一个满足点边权和比大于mid的回路,则二分判断条件为

(Vp为最优简单回路的点集,Ep为最优简单回路的边集)

稍微变换一下形式

这个判断条件依旧不好计算,因为我们二分的目的就是为了把最优化问题转换为判断性问题,但是对于该条件,我们除了枚举所有的简单回路,没有任何切入点

转念一想,最后这个大于0似乎暗藏玄机,又和回路联系在一起

不由得让人想到判断图是否存在正权回路(可以直接取相反数转化为判断负权回路)

为了把问题往这个方向转,我们尝试把点权下放到边权

把每条边边权设置为 -(它要通往的点的点权-mid*它原本的边权)

但是这样又会有一个新的问题,如果我们最后选出来的回路是这个样子

[USACO07DEC] Sightseeing Cows G(分数规划+负权回路判定),算法,数学,SPFA,二分,C++

这样不就会重复计算点权了吗?

事实上这种情况是不存在的

我们可以感性的证明一下:

出现重复点的简单回路,一定可以拆解成若干初级回路(无重复点、无重复边)

整个回路最终的比率一定不会超过其中比率最大的初级回路((a+b)/(c+d)<=max(a/c,b/d),似乎在小学奥数里面叫糖水不等式?)(而且整个回路的比率的分子还会减去重复点的点权)

所以,我们选择一定是选择简单回路里面最优的初级回路

至此,我们就可以下放点权了

愉快地使用SPFA进行负权回路判断

代码:文章来源地址https://www.toymoban.com/news/detail-685611.html

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define N 1005
#define M 10005
#define INF 1000000000
int n,m;
int F[N];
struct enode{
	int u,v,w;
}E[M];
int fir[N],to[M],nxt[M],cnt;
double cd[M];
void adde(int a,int b,double c)
{
	to[++cnt]=b;cd[cnt]=c;nxt[cnt]=fir[a];fir[a]=cnt;
}
double dis[N];
int con[N];
bool inq[N];
queue<int> Q;
bool check()
{
	int i;
	for(i=1;i<=n;i++)dis[i]=INF;
	for(i=1;i<=n;i++)con[i]=0;
	for(i=1;i<=n;i++)inq[i]=0;
	for(i=1;i<=n;i++){
		if(dis[i]==INF){
			dis[i]=0;inq[i]=1;
			Q.push(i);
			while(!Q.empty()){
				int u=Q.front();Q.pop();inq[u]=0;
				for(int p=fir[u];p;p=nxt[p]){
					int v=to[p];
					double w=cd[p];
					if(dis[u]+w<dis[v]){
						dis[v]=dis[u]+w;
						con[v]++;
						if(!inq[v]){Q.push(v);inq[v]=1;}
						if(con[v]>=n)return 1;
					}
				}
			}
		}
	}
	return 0;
}
int main()
{
	int i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
		scanf("%d",&F[i]);
	for(i=1;i<=m;i++)
		scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
	double l=0,r=1000,mid;
	while(r-l>1e-3){
		mid=(l+r)/2;
		cnt=0;
		for(i=1;i<=n;i++)fir[i]=0;
		for(i=1;i<=m;i++)
			adde(E[i].u,E[i].v,-(1.0*F[E[i].v]-mid*E[i].w));
		if(check())
			l=mid;
		else
			r=mid;
	}
	printf("%.2f",l);
}

到了这里,关于[USACO07DEC] Sightseeing Cows G(分数规划+负权回路判定)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • P3405 [USACO16DEC] Cities and States S

    Farmer John 有若干头奶牛。为了训练奶牛们的智力,Farmer John 在谷仓的墙上放了一张美国地图。地图上表明了每个城市及其所在州的代码(前两位大写字母)。 由于奶牛在谷仓里花了很多时间看这张地图,他们开始注意到一些奇怪的关系。例如,FLINT 的前两个字母就是 MIAMI 所

    2024年03月20日
    浏览(66)
  • P2921 [USACO08DEC] Trick or Treat on the Farm G

    Portal. 每只奶牛的终止条件是到达自己已经访问过的点,换言之,就是该奶牛的路线构成了一个环。并且,每一个房间通往的房间都是固定且唯一的,所以说只要进入的这个房间在环上,这个房间之后会获得的糖果数已经固定了。 我们开一个数组 s 记录当前位置的糖果数量,

    2024年02月06日
    浏览(237)
  • 蓝桥杯-回路计数(状态压缩、动态规划)

    蓝桥学院由 21 21 21 栋教学楼组成,教学楼编号 11 11 11 ​​ 到 21 21 21 ​​。对于两栋教学楼 a a a 和 b b b ​,当 a a a 和 b b b 互质时, a a a 和 b b b 之间有一条走廊直接相连,两个方向皆可通行,否则没有直接连接的走廊。 小蓝现在在第一栋教学楼,他想要访问每栋教学楼正

    2024年02月08日
    浏览(60)
  • 【蓝桥杯冲冲冲】动态规划初步[USACO2006 OPEN] 县集市

    [USACO2006 OPEN] 县集市 The County Fair 每年,FJ 都喜欢去参加县集市,集市上有 n n n 个展位,每个摊位 i i i 都会在当天的特定时间 p i p_i p i ​ 发放精美的礼品。FJ 已经听说了这一点,他希望能收集尽可能多的礼品和他的奶牛们一起分享。要想获得摊位 i i i 发放的礼品,FJ 必须确

    2024年01月22日
    浏览(35)
  • 基本技巧——分数规划 学习笔记

    分数规划用来求一个分式的极值。 具体的,给定 (n) 个元素,每个元素有属性 (a_i,b_i) ,求一个集合 (Pin[1,n]) ,最大/最小化比率:$$dfrac{sum_{iin P}a_i}{sum_{iin P}b_i}$$ 二分法 假设我们要求最大值(求最小值的方法和求最大值的方法类似),二分一个 (text{mid}) ,然后推

    2024年02月08日
    浏览(44)
  • Atcoder Beginner Contest 324 F Beautiful Path 题解-分数规划

    为了更好的阅读体验,请点击这里 分数规划小技巧: 尽可能将式子写成存在某种取值,使得不等式成立的形式。 不然可能需要绕几个弯才能想出来。 题目链接 题目大意:给出一个 DAG,每条边有一个 (b_i, c_i) ,保证从编号小的边向编号大的边连边,且 (1) 到 (n) 必有路径

    2024年02月08日
    浏览(38)
  • 第三章 图论 No.6负环之01分数规划与特殊建图方式

    裸题:904. 虫洞 904. 虫洞 - AcWing题库 这个==真的服,调半天,还有,邻接表的大小又设置错了 01分数规划:361. 观光奶牛 361. 观光奶牛 - AcWing题库 在图论问题中,所有形如:某个部分之和除以某个部分之和最大的问题,被称为01分数规划,通常使用二分解决这类问题 根据题意

    2024年02月13日
    浏览(41)
  • 动态规划Day07

    卡码网:57. 爬楼梯(opens new window) 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 = m n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述:输入共一行,包含两个正整数,分别表示n, m 输出描述:输出一个整数,表

    2024年01月24日
    浏览(37)
  • NC51101 Lost Cows

    题目链接 题目描述 (N (2 leq N leq 8,000)) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood \\\'watering hole\\\' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their bran

    2024年02月02日
    浏览(31)
  • 贝尔曼福特算法——负权值单源最短路径

    title: 贝尔曼福特算法——负权值单源最短路径 date: 2023-05-16 11:42:26 tags: 数据结构与算法 **问题:**具有负权值非环图的单源最短路径算法 git地址:https://github.com/944613709/HIT-Data-Structures-and-Algorithms 对图中的边进行V-1轮遍历,对所有的边松弛(对每条边v1-v2,如果d[v2]+Weight(v1-v2)

    2024年02月14日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包