首页 > 其他分享 >floyd 专题 - 2

floyd 专题 - 2

时间:2023-08-30 18:22:25浏览次数:34  
标签:专题 const int db 矩阵 floyd dis

8.29 模拟赛小记。


A.时间复杂度,洛谷原题指路:P1522 [USACO2.4] 牛的旅行 Cow Tours

首先为啥从 100pts -> 88-> 77。因为打完第一遍之后感觉思路不太对,少考虑了一个部分,然后加了一个并查集。挂分是因为连通块合并写挂了(基础还能错是我有罪)。所以属实没想到第一遍能 AC,那份码在洛谷上会被 hack 掉,oj 数据这么弱啊 qwq。

后来看原发现我在远古时期(指两年前)就提交过,但思路同第一份一样错了所以也被 hack 了。没记错的话是一本通上有这道题,但那上面的思路考虑的就不全,书上的码会被卡掉。题外话,怪不得现在入门都不看一本通了。

以下是正文。

求将两个不在同一牧场的点连到一起后新牧场直径的最小值,先考虑用并查集预处理连通块。

暴力的枚举,先跑 floyd 初始化。然后用 mx[i] 表示从 i 号点出发到距离它最远的点的距离,t[i] 表示 i 号连通块的直径(该连通块内所有点的 mx[i] 的 max)。

最后考虑依次枚举考虑如果两个点 i、j 不在同一连通块中,它们之间如果连起来后得到的新牧场的直径大小。

新牧场的直径大小考虑三种情况,i 号连通块的直径,j 号联通块的直径,i 号点能到的最远距离加上 j 号点能到的最远距离再加上 i、j 之间的距离。

minn = min(minn, max(mx[i] + mx[j] + dis(i, j), max(t[fd(i)], t[fd(j)])));

#include<bits/stdc++.h>
using namespace std;
typedef double db;
const int N = 202;
const db inf = 0x3fffffff;
char c[N];
int n, m;
int fa[N];
db x[N], y[N];
db f[N][N], mx[N], t[N];
db dis(int i, int j) {return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));}
int fd(int x)
{
	if(fa[x] == x) return x;
	return fa[x] = fd(fa[x]);
} 
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ )
	{
		fa[i] = i;
		scanf("%lf%lf", &x[i], &y[i]);
	}
	for(int i = 1; i <= n; i ++ )
	{
		scanf("%s", c + 1);
		for(int j = 1; j <= n; j ++ )
		{ 
			if(c[j] == '1')
			{
				f[i][j] = dis(i, j);
				fa[fd(i)] = fd(j);
			}
			else if(i != j) f[i][j] = inf;
		}
	}
	for(int k = 1; k <= n; k ++ )
		for(int i = 1; i <= n; i ++ )
			for(int j = 1; j <= n; j ++ ) f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
	for(int i = 1; i <= n; i ++ )
	{
		for(int j = 1; j <= n; j ++ ) if(fd(i) == fd(j)) mx[i] = max(mx[i], f[i][j]);
		t[fd(i)] = max(t[fd(i)], mx[i]);
	}
	db minn = inf;
	for(int i = 1; i <= n; i ++ )
		for(int j = 1; j <= n; j ++ )
			if(fd(i) != fd(j))
			{
				minn = min(minn, max(mx[i] + mx[j] + dis(i, j), max(t[fd(i)], t[fd(j)])));
			}
	printf("%.6lf", minn);
	return 0;
}

B.“快速米”变速自行车-认真分析数据范围,洛谷原题指路:P1613 跑路

一看到 2^k 就想到倍增了,还是很好想的。f[i][j][k] 表示从 i 到 j 行驶 \(2 ^ k\) 是否能到达,若 \(2 ^ {k - 1}\) 能到达则 \(2^k\) 也可以。再跑一遍 floyd 就可以。

以及,你考虑输出 1 是能骗很多分的。想一想就会发现其他答案的数据会比较难造。

#include<bits/stdc++.h>
using namespace std;
const int N = 55;
const int K = 70;
int n, m, s, t;
int f[N][N][K], dis[N][N];
int main()
{
    scanf("%d%d", &n, &m);
    memset(dis, 0x3f, sizeof dis);
    for(int i = 1; i <= m; i ++ )
    {
        scanf("%d%d", &s, &t);
        f[s][t][0] = 1;
        dis[s][t] = 1;
    }
    for(int t = 0; t < 64; t ++ )
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ )
                for(int k = 1; k <= n; k ++ )
                    if(f[i][k][t] && f[k][j][t])
                    {
                        f[i][j][t + 1] = 1;
                        dis[i][j] = 1;
                    }
    for(int k = 1; k <= n; k ++ )
    	for(int i = 1; i <= n; i ++ )
    		for(int j = 1; j <= n; j ++ )
    			dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    printf("%d", dis[1][n]);
}

C.最短路-认真读题防陷阱,洛谷原题指路:P2886 [USACO07NOV] Cow Relays G

1.要读好题,本题的输入顺序是数 w, u, v。

2.oj 上输出 -1 有 14pts。我赛时一直在调 A 导致忘了交码了。

让你正好走 n 条边。边数为 100,n 为 1e6,直接跑 floyd 一定会超时。所以考虑优化重复跑的过程,不难想到倍增。

然后就会发现是跑很多遍 floyd,跑了之后更新矩阵、再跑。会发现这个过程有点类似于矩阵乘法。不会矩阵乘法快速幂的请移步去看板子:P3390 【模板】矩阵快速幂

floyd 和矩阵乘法都有 3 个 for,这就有点异曲同工之妙了。

所以以类似矩阵乘法的方式,快速幂里面套跑 floyd 的新矩阵每次转移就好力!

注意:

1.一共需要转移 n - 1 次而不是 n 次。

2.边数只有 100,给的点编号却有 1000,所以需要离散化。

3.oj 上需要判断 -1,洛谷上不用。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int n, t, s, e;
int tot, v[N];
struct M{
	int a[120][120];
	M operator *(const M &x) const
	{
		M b;
		memset(b.a, inf, sizeof b.a);
		for(int k = 1; k <= tot; k ++ )
			for(int i = 1; i <= tot; i ++ )
				for(int j = 1; j <= tot; j ++ )
					b.a[i][j] = min(b.a[i][j], a[i][k] + x.a[k][j]);
		return b;
	}
}dis, ans;
int main()
{
	memset(dis.a, inf, sizeof dis.a);
	scanf("%d%d%d%d", &n, &t, &s, &e);
	while(t -- )
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		if(! v[y]) v[y] = ++ tot;
		if(! v[z]) v[z] = ++ tot;
		dis.a[v[y]][v[z]] = dis.a[v[z]][v[y]] = x;
	}
	n --;
	ans = dis;
	while(n)
	{
		if(n & 1) ans = ans * dis;
		dis = dis * dis;
		n >>= 1;
	}
	printf("%d", ans.a[v[s]][v[e]]);
	return 0;
}

标签:专题,const,int,db,矩阵,floyd,dis
From: https://www.cnblogs.com/Moyyer-suiy/p/17667986.html

相关文章

  • HCIE-广域承载解决方案专题01-SR
    HCIE-广域承载解决方案专题01-SR基本概念1SR(SegmentRouting)概述1.1MPLSLDP与RSVP-TE存在的问题MPLSLDPLDP本身并无算路能力,需依赖IGP进行路径计算控制面需要IGP及LDP,设备之间需要发送大量的消息来维持邻居关系及路径状态,浪费了链路带宽及设备资源若LDP与IGP切换过......
  • floyd 专题
    更进一步的感悟floyd内涵!了解&理解floyd:floyd算法,常用于求多源最短路,O(n^3)。本质是动态规划。两个点,通过找中转点更新答案。三个for。其中第一个for枚举k表示除了起点终点外只允许前走1~k个点的答案。另外两个for枚举起点终点。例题1:P1119灾后重建:加强......
  • 【专题】2022品牌营销决策解决方案报告PDF合集分享(附原数据表)
    全文链接:https://tecdat.cn/?p=33511根据报告合集显示,在消费者的亲友分享、社交平台、订单评价等环节,00后表现出活跃的参与度,而90后和95后在部分环节也较为活跃。相比之下,70后和80后在分享中的参与度最低,主要以亲友分享为主。阅读原文,获取专题报告合集全文,解锁文末335份品牌营销......
  • 【专题】2023品牌内容营销洞察报告PDF合集分享(附原数据表)
    全文链接:https://tecdat.cn/?p=33511根据报告合集显示,在消费者的亲友分享、社交平台、订单评价等环节,00后表现出活跃的参与度,而90后和95后在部分环节也较为活跃。相比之下,70后和80后在分享中的参与度最低,主要以亲友分享为主。阅读原文,获取专题报告合集全文,解锁文末335份品牌营销......
  • 【专题】洞察营销的战略优势与实操报告PDF合集分享(附原数据表)
    全文链接:https://tecdat.cn/?p=33511根据报告合集显示,在消费者的亲友分享、社交平台、订单评价等环节,00后表现出活跃的参与度,而90后和95后在部分环节也较为活跃。相比之下,70后和80后在分享中的参与度最低,主要以亲友分享为主。阅读原文,获取专题报告合集全文,解锁文末335份品牌营销......
  • 城市生命线专题周丨宏电内涝立体监测系统,构筑城市防汛智慧屏障
    方案背景在城市化进程不断推进和极端降雨事件频发的双重影响下,城市“看海”现象屡屡发生。以往的传统方法如整治河道、改造地下管网、增加排涝设施等已经不足以很好地解决现代城市内涝问题,随着物联网技术的快速发展和深入应用,使得以信息化的手段实现城市内涝的监测预警与模拟预测成......
  • 【Ehcache技术专题】「入门到精通」带你一起从零基础进行分析和开发Ehcache框架的实战
    缓存大小的设置缓存大小的限制可以设置在CacheManager上,也可以设置在单个的Cache上。我们可以设置缓存使用内存的大小,也可以设置缓存使用磁盘的大小,但是使用堆内存的大小是必须设置的,其它可设可不设,默认不设就是无限制。在设置缓存大小的时候,我们可以设置缓存使用某一个存储器的最......
  • RS232串口专题
    启动串口调试助手项目运行截图基础类封装数据类型转换类usingSystem;usingSystem.Text;namespaceSerialPortHelperDemo{///<summary>///16进制使用的隔离符枚举///</summary>publicenumEnum16Hex{None,//无Blank,/......
  • 【Ehcache技术专题】「入门到精通」带你一起从零基础进行分析和开发Ehcache框架的实战
    Ehcache的存储方式Ehcache中对于缓存的存储主要有三种方式:分别是堆内存、非堆内存和磁盘。其中非堆内存是针对于企业版Ehcache才有的功能,它可以不受JavaGC的影响,能够创建很大的缓存。堆内存(MemoryStore)我们通常所有的MemoryStore实际上就是堆内存存储。MemoryStore总是可用的,所有......
  • 《算法笔记》树与二叉树专题练习
    1、复原二叉树(由前序和中序求后序)题目描述小明在做数据结构的作业,其中一题是给你一棵二叉树的前序遍历和中序遍历结果,要求你写出这棵二叉树的后序遍历结果。输入输入包含多组测试数据。每组输入包含两个字符串,分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写......