【算法每日一练]-图论（保姆级教程篇14 ）#会议（模板题） #医院设置 #虫洞 #无序字母对 #旅行计划 #最优贸易

目录

今日知识点：

求数的重心先dfs出d[1]和cnt[i]，然后从1进行dp求解所有d[i]

两两点配对的建图方式，检查是否有环

无向图欧拉路径+路径输出

topo+dp求以i为终点的游览城市数

建立分层图转化盈利问题成求最长路

会议（模板题）

医院设置 

虫洞

无序字母对 

旅行计划

最优贸易

        

        

        

会议（模板题）

         

 思路：

补充：首先，阅读题目可以看出来，这道题目实际上就是求树的重心。

树的重心：找到一个点，其所有的子树中最大的子树节点数最少，那么这个点就是这棵树的重心，删去重心后，达到的效果是生成的多棵树尽可能平衡。

啊？不是n-1边n点的无向图吗？怎么就一定是棵树了呢？万一是“X”型或者“米”型的无向图呢，哈哈我可太聪明了。

你直接从任意一个点做根开始，然后把该点其余的分支点都掰到下面去。也就是说把其余的子树都扭动到下面去，这不就是一颗树了吗。明白了吗！

OK，怎么解这道题呢？

举个例子：

我们不妨设置d[i]表示以此点为根的所有点总距离和，cnt[i]表示以此为根的节点数

我们首先知道d[1]=16,cnt[1]=10我们来看d[2]应该怎么求,我们发现相对于d[1]来说，如果设2为最佳点,2,5,6其距离-1，剩下的1,4,3,7,8,9,10到其距离+1。

故：d[2]=d[1] - 3 + 7 =20

其中3是子根2对应的节点数cnt[2]，7是1为子根对应的节点数cnt[1]-cnt[2]

得：d[i]=d[fa]-cnt[i]+(cnt[1]-cnt[i])

那么只需要先dfs求出来d[1]和每个点的cnt[i]。然后就可以进行dp最终求出所有点的d[i]。

 

#include <bits/stdc++.h>
using namespace std;
const int N=50005;
int minn=0x3f3f3f3f,ans,n,d[N],cnt[N];
vector<int>ve[N];
void dfs(int u,int fa,int len){//一定别走fa回去
	cnt[u]++;//先加上自己
	for(int i=0;i<ve[u].size();i++){
		int v=ve[u][i];
		if(v==fa)continue;
		dfs(v,u,len+1);//先求孩子的cnt，之后求自己cnt
		cnt[u]+=cnt[v];
	}
	d[1]+=len;//最后求d[1]
}
void dp(int u,int fa){
	for(int i=0;i<ve[u].size();i++){
		int v=ve[u][i];
		if(v==fa)continue;
		d[v]=d[u]-2*cnt[v]+cnt[1];
		dp(v,u);//这里对自己进行转移更新，再对孩子的更新
	}
}
int main(){
	cin>>n;int a,b;
	for(int i=1;i<n;i++){
		cin>>a>>b;
		ve[a].push_back(b);
		ve[b].push_back(a);
	}
	dfs(1,0,0);
	dp(1,0);
	for(int i=1;i<=n;i++){
		if(d[i]<minn)
			minn=d[i],ans=i;
	}
	cout<<ans<<" "<<minn;
}

上面我打注释的地方一定要理解 

        

        

医院设置 

 

 

思路：

还是一道求树的重心题。不过是每个点都有一个权值。那么把权值当成“另一个世界的节点数”就好了。然后不断求cnt，之后dp就行。 

#include <bits/stdc++.h>
using namespace std;
const int N=500;
int ans=0x3f3f3f3f,n,d[N],cnt[N],w[N];
vector<int>ve[N];
void dfs(int u,int fa,int len){
	cnt[u]=w[u];//这里还是先加自己
	for(int i=0;i<ve[u].size();i++){
		int v=ve[u][i];
		if(v==fa)continue;
		dfs(v,u,len+1);
		cnt[u]+=cnt[v];
	}
	d[1]+=len*w[u];//更新d[1]也要变一下
}
void dp(int u,int fa){
	for(int i=0;i<ve[u].size();i++){
		int v=ve[u][i];
		if(v==fa)continue;
		d[v]=d[u]+cnt[1]-cnt[v]*2;
		dp(v,u);
	}
	ans=min(ans,d[u]);
}
int main(){
	cin>>n;int c,a,b;
	for(int i=1;i<=n;i++){
		cin>>c>>a>>b;
		w[i]=c;//注意输入方式
		if(a)ve[i].push_back(a),ve[a].push_back(i);
		if(b)ve[i].push_back(b),ve[b].push_back(i);
	}
	dfs(1,0,0);
	dp(1,0);
	cout<<ans;
}

        

        

虫洞

        

思路：
首先分析一下：第一是如何去建图，其次是如何找方案

找方案的话就直接暴力配对吧(题上的数据量不大，肯定要暴力)，然后就是建图要保证即要方便图的还原（因为配对后还要回溯呢），又要方便跑图（每次建好都要跑一次看看是否存在一个循环），最后就是坐标范围非常大啊，所以要巧妙一点。

首先：我们对这些黑洞位置排序，只关注同行的，同行中能从A黑洞走到B黑洞的就标记一下A能到B(使用唯一的ID号映射)。

之后：dfs选择配对方案，然后dfs的for函数也是很巧妙：首先要保证不能和前面重复（相当于1号黑洞可以找2，3，4，但是之后4号一定不能再找1，2，3了，所以要保证递增）然后是g[i]=k;g[k]=i这样建图（因为是两两配对，所以每个起点最多只有一个尾点）。最后是建好图后直接从每个黑洞ID号为起点进行查询即可。

最后是检查函数cycle：从起点一直走，走到走过的就可以停止了

#include <bits/stdc++.h>
using namespace std;
int ans,n,to[20],vis[20],g[20];
struct node{int x,y;}p[20];

bool cmp(node a,node b){
	return (a.y<b.y)||(a.y==b.y&&a.x<b.x);
}

int cycle(int x){
	while(to[x]){//走到下一个黑洞，如果有的话
		if(vis[x])return 1;
		vis[x]=1;
		x=g[to[x]];//终点变成起点（如果有的话）
	}
	return 0;
}
void dfs(int k){
	if(k>n){
		int f=0;
		for(int i=1;i<=n;i++){//巧妙3：直接从黑洞号开始就行
			memset(vis,0,sizeof(vis));
			f|=cycle(i);//巧妙4：这里之所以这么写，是为了防止被标记过1后又被0覆盖掉
		}
		ans+=f;
		return ;
	}
	if(g[k])dfs(k+1);
	else {
		for(int i=k+1;i<=n;i++){//巧妙1：去重
			if(g[i])continue;
			g[i]=k;g[k]=i;//巧妙2：设置两个黑洞的关系
			dfs(k+1);
			g[i]=g[k]=0;//清除两个黑洞之间的关系
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>p[i].x>>p[i].y;
	sort(p+1,p+1+n,cmp);
	for(int i=1;i<=n-1;i++){
		if(p[i].y==p[i+1].y) to[i]=i+1;//把相邻且在同一航 行的标记在一起
	}
	dfs(1);
	cout<<ans;
	
}

首先是方案配对，然后是建图策略(至多两两配对)，最后到检查循环都是非常精妙的 ，值得细看

         

        

无序字母对 

思路： 

这里就可以发现实际上就是在找欧拉路，首先每个字符就是代表的图中的某一个点，底下输入的字符串
就代表两点之间有连通，构造字符串就是在找输出一笔画回路，明白这个代码就很简单了

 下面是代码：基于无向图得欧拉路径问题+路径输出

无向图得欧拉路径：连通图，且没有度为奇数的节点(欧拉回路) 或 只有两个2个度为奇数的节点 

#include <bits/stdc++.h>
using namespace std;
const int N=300;
int g[N][N],fa[N],du[N],m;
char ans[N*N],s[N];
int find(int x)
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];//返回祖先 
}

void dfs(int x){
	for(int i=0;i<N;i++)
		if(g[x][i]){
		g[x][i]=g[i][x]=0;//取过了这个字母就情空，避免走环 g=0相当于vis=1
		dfs(i);
	}
	ans[m--]=x;
}

int main()
{
	cin>>m;
    for(int i=0; i<N; i++) fa[i]=i;
    for(int i=1; i<=m; i++){
    	scanf("%s",s);
    	g[s[0]][s[1]]=g[s[1]][s[0]]=1;
        du[s[0]]++;du[s[1]]++;
        int f1=find(s[0]),f2=find(s[1]);//合并建树
        fa[f1]=f2;
	}
//判断是否连通
	int tmp=0;
	for(int i=0;i<N;i++)
		if(fa[i]==i&&du[i])tmp++;
	if(tmp!=1){
		cout<<"No Solution";return 0;
	}
//是否存在欧拉路径	
	int f=0,rt=0;
	for(int i=0;i<N;i++){
		if(du[i]&1){
			f++;	//一边统计多少个奇数度点，一边找奇数的rt做起点
			if(!rt)rt=i;
		}
	}
	if(f&&f!=2){
		cout<<"No Solution";return 0;
	}
//按照字典序最小开始输出路径
	if(!rt){//rt不能从0开始
		for(int i=0;i<N;i++){//按照ASCII找最小的起点rt
			if(du[i]){
				rt=i;break;
			}
		}
	}
	dfs(rt);
	cout<<ans;

}

        

         

旅行计划

 

思路：

题上问以i点为终点的最多游览的城市数。非常类似之前说过的“食物链计数”那道题。

设置f[i]表示以i为终点的最多的游览城市数。那么从入度为0的点开始进行正向topo即可。

顺便再补充一个方向：如果设置f[i]表示以i为起点的最多的游览城市数。那么肯定不能正向topo。

这个时候需要用dfs进行回溯式topo处理。

#include<bits/stdc++.h> 
using namespace std;
const int N=100005;
vector <int>ve[N];
queue<int> q;
int n,m,ans,f[N],in[N],out[N];

int main(){
	cin>>n>>m;int x,y;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		ve[x].push_back(y);
		in[y]++;out[x]++;
	}
	for(int i=1;i<=n;i++){
		if(in[i]==0){q.push(i);f[i]=1;}
	}
	while(q.size()){//进行拓扑排序
		int cur=q.front();q.pop();
		for(int i=0,sz=ve[cur].size();i<sz;i++){
			int v=ve[cur][i];
			f[v]=f[cur]+1;in[v]--;
			if(in[v]==0) q.push(v);
		}		
	}

	for(int i=1;i<=n;i++)
	cout<<f[i]<<'\n';
	
	
	return 0;
}

        

         

最优贸易

 

思路：

 每个点都可以不卖不买，买，或卖这3种状态，那么分层图自然最合适。

最上面的层之间不论怎么跑动一定不会赚钱或亏钱。只有在层之间移动才能赚钱或亏钱。

也就是层内关系权值为0，层间非0.

然后就转化成spfa求最长路即可。 

#include <bits/stdc++.h> 
using namespace std;
const int N=1e5+5;
int cnt,head[N*3];
int dis[N*3];
bool vis[N*3];
struct Edge{ int to,w,next;}e[250000*3];
void add(int u,int v,int w) { e[++cnt]=(Edge){v,w,head[u]}; head[u]=cnt;}
void spfa(int s)
{
    memset(dis,-0x3f,sizeof(dis));
    queue<int>Q;
    dis[s]=0;vis[s]=1;
    Q.push(s);
    while(!Q.empty())
    {
		int u=Q.front(); Q.pop();
		vis[u]=0;
	    for(int i=head[u];i;i=e[i].next)
	    {
	        int v=e[i].to,w=e[i].w;
	        if(dis[v]<dis[u]+w) {
	        	dis[v]=dis[u]+w;
				if(vis[v])continue;
				Q.push(v);vis[v]=1;	
			}
	    }
    }    
}

int main()
{
	int n,m,price;
	cin>>n>>m; 
	for(int i=1;i<=n;i++){
		cin>>price;
		add(i,i+n,-price);//在层之间建立关系
		add(i+n,i+n*2,price);
	}
    int u,v,c;
    for(int i=0;i<m;++i)
    {
    	cin>>u>>v>>c;
    	add(u,v,0);add(u+n,v+n,0);add(u+2*n,v+2*n,0);//建立 分层图（层内图）
    	if(c==2){
    	add(v,u,0);add(v+n,u+n,0);add(v+2*n,u+2*n,0);
		}
    }
    spfa(1);
    printf("%d",dis[n+2*n]);
    return 0;
}

然后做完这道题，可以很明显发现和之前做过的“飞行路线”一题很像。那道题中是层内关系的权值非0，层间的关系权值为0，最后在最下面的层找答案即可。本题刚好反过来。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/300091.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

向日葵远程工具安装Mysql5.7的安装与配置

向日葵远程工具安装Mysql5.7的安装与配置

文章目录 一、向日葵远程工具安装二、Mysql5.7的安装与配置2.1解压2.2再把my.ini文件放入解压后的文件里面2.3.改变my.ini文件2.4.用管理员身份运行cmd&#xff0c;进入bin文件夹里&#xff0c;运行"mysqld install"命令&#xff0c;出现以下就说明成功了2.5.注册完s…
阅读更多...
20. Mysql 游标的定义和使用

20. Mysql 游标的定义和使用

文章目录 概念游标的基本语法声明游标打开游标使用游标关闭游标精选示例 总结 概念 游标&#xff08;Cursor&#xff09;是一种数据库对象&#xff0c;可以指向存储在数据库表中的数据行指针。用于在 sql 语句的执行过程中&#xff0c;通过对查询结果集进行逐行的操作和访问。…
阅读更多...
【大数据进阶第三阶段之Hive学习笔记】Hive常用命令和属性配置

【大数据进阶第三阶段之Hive学习笔记】Hive常用命令和属性配置

目录 1、Hive安装 2、HiveJDBC访问 2.1、启动hiveserver2服务 2.2、连接hiveserver2服务 2.3、注意 3、Hive常用交互命令 3.1、“-e”不进入hive的交互窗口执行sql语句 3.2、“-f”执行脚本中sql语句 4、Hive其他命令操作 4.1、退出hive窗口 4.2、在hive cli命令窗口…
阅读更多...
rosbag 源码阅读笔记-1

rosbag 源码阅读笔记-1

这篇文字想通过在自己的机器上查找rosbag的源码在哪里&#xff08;而不是通过google搜索&#xff09;&#xff0c;来和大家分享一些ros和python的常用命令&#xff0c;了解一下rosbag的调用过程。 怎么查到源码在哪里 当然我们可以直接上ros的官网去查看&#xff0c;路径在这…
阅读更多...
静态网页设计——科学家网（HTML+CSS+JavaScript）(dw、sublime Text、webstorm、HBuilder X)

静态网页设计——科学家网（HTML+CSS+JavaScript）(dw、sublime Text、webstorm、HBuilder X)

前言 声明&#xff1a;该文章只是做技术分享&#xff0c;若侵权请联系我删除。&#xff01;&#xff01; 感谢大佬的视频&#xff1a;https://www.bilibili.com/video/BV1wg4y1Q7qm/?vd_source5f425e0074a7f92921f53ab87712357b 源码&#xff1a;https://space.bilibili.com…
阅读更多...
基于Springboot的在线考试系统

基于Springboot的在线考试系统

点击以下链接获取源码&#xff1a; https://download.csdn.net/download/qq_64505944/88499371 mysql5、mysql8都可使用 内含配置教程文档&#xff0c;一步一步配置 Springboot所写 管理员页面 学生页面
阅读更多...
jetson deepstream 解码接入编码输出

jetson deepstream 解码接入编码输出

不需要编解码输出画面的直接到7 使用就行 1 jetson主板编译工具 在jetson主板上安装gstreamer工具链&#xff0c;编译opencv sudo apt install -y libgstreamer1.0-dev libgstreamer-plugins-base1.0-dev gstreamer1.0-plugins-ugly gstreamer1.0-rtsp python3-dev pytho…
阅读更多...
【信息论与编码】习题-判断题-第三部分

【信息论与编码】习题-判断题-第三部分

目录 判断题48. 利用状态极限稳态分布概率和符号的状态一步转移概率来求m阶马尔可夫信源的极限熵。49. 连续信源或模拟信号的信源编码的理论基础是限失真信源编码定理 。50. 具有一一对应关系的无噪信道的信道容量CH(X)。51. 在游程编码过程中&#xff0c;“0”游程和“1”游程…
阅读更多...
PHP进阶-实现网站的QQ授权登录

PHP进阶-实现网站的QQ授权登录

授权登录是站点开发常见的应用场景&#xff0c;通过社交媒体一键授权可以跳过注册站点账户的繁琐操作。本文将讲解如何用PHP实现QQ授权登录。首先&#xff0c;我们需要申请QQ互联开发者账号获得APPID和密钥&#xff1b;接着&#xff0c;我们下载QQ官方SDK&#xff1a;PHP SDK v…
阅读更多...
【VTKExamples::Visualization】第一期 Arbitrary3DCursor

【VTKExamples::Visualization】第一期 Arbitrary3DCursor

很高兴在雪易的CSDN遇见你 VTK技术爱好者 QQ&#xff1a;870202403 前言 本文分享Example中Visualization模块中的Arbitrary3DCursor样例&#xff0c;主要解析vtkProbefileter&#xff0c;希望对各位小伙伴有所帮助&#xff01; 感谢各位小伙伴的点赞关注&#xff0c;小易会…
阅读更多...
大学物理实验重点——霍尔效应

大学物理实验重点——霍尔效应

霍尔系数 霍尔元件灵敏度&#xff0c;愈大愈好 负效应&#xff1a; 1. 不等位电势 V0&#xff1a;两个霍尔电极不可能绝对对 称地焊在霍尔元件两侧&#xff08;图 2&#xff09;、霍尔元件电阻率不均匀、工作电极的端面接触不良都 可能造成 C、D 两极不处在同一等位面上。R0 确…
阅读更多...
XCTF：凯撒大帝在培根里藏了什么[WriteUP]

XCTF：凯撒大帝在培根里藏了什么[WriteUP]

密文&#xff1a; ABBABAABBAAAAABABABAABABBAAAAABAABBAAABAABBBABBAABABBABABAAABABBBAABAABABABBBAABBABAA 根据题目提示&#xff0c;应该有两种加密算法 1.培根加密 2.凯撒加密 根据语境&#xff0c;且密文与凯撒加密后的密文不符合&#xff0c;先尝试培根解密 培根解…
阅读更多...
大数据时代必备技能！Shell脚本学习网站助你一臂之力！

大数据时代必备技能！Shell脚本学习网站助你一臂之力！

介绍&#xff1a;Shell脚本是一种用于自动化任务的脚本语言&#xff0c;它使用Shell命令来执行一系列操作。Shell脚本通常以.sh为扩展名&#xff0c;并使用#!/bin/bash作为第一行来指定使用的Shell解释器。 在Shell脚本中&#xff0c;我们可以使用各种命令和控制结构来实现自动…
阅读更多...
Hadolint：Lint Dockerfile 的完整指南

Hadolint：Lint Dockerfile 的完整指南

想学习如何使用 Hadolint 对 Dockerfile 进行 lint 处理吗&#xff1f;这篇博文将向您展示如何操作。这是关于 Dockerfile linting 的完整指南。 通过对 Dockerfile 进行 lint 检查&#xff0c;您可以及早发现错误和问题&#xff0c;并确保它们遵循最佳实践。 什么是Hadolint…
阅读更多...
数据结构期中模拟

数据结构期中模拟

一、填空题 1.二叉树就是度为 2 的树。&#xff08;F&#xff09; 二叉树的度<2 2.线性表采用链式存储表示时&#xff0c;所有结点之间的存储单元地址可以连续也可以不连续。(T) 在顺序表中&#xff0c;逻辑上相邻的元素&#xff0c;其物理位置一定相邻。在单链表中&#x…
阅读更多...
java案例知识点

java案例知识点

一.会话技术 概念 技术 二.跨域 三.过滤器 四.拦截器
阅读更多...
电脑丢失dll文件怎么办，dll修复工具可一键修复dll问题

电脑丢失dll文件怎么办，dll修复工具可一键修复dll问题

在计算机使用过程中&#xff0c;我们经常会遇到一些错误提示&#xff0c;其中最常见的就是“找不到指定的模块”或“无法找到某某.dll文件”。这种情况通常是由于dll文件丢失或损坏导致的。那么&#xff0c;究竟是什么原因导致了dll文件的丢失呢&#xff1f;又该如何预防dll文件…
阅读更多...
Linux 编译安装 Nginx

Linux 编译安装 Nginx

目录 一、前言二、四种安装方式介绍三、本文安装方式&#xff1a;源码安装3.1、安装依赖库3.2、开始安装 Nginx3.3、Nginx 相关操作3.4、把 Nginx 注册成系统服务 四、结尾 一、前言 Nginx 是一款轻量级的 Web 服务器、[反向代理]服务器&#xff0c;由于它的内存占用少&#xf…
阅读更多...
CentOS中开启mysql挂载

CentOS中开启mysql挂载

挂载的作用其实说白了就是备份。防止数据库文件损害或者数据库被误删导致数据丢失。 创建一个文件名为my.cnf内容如下 # Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved. # # This program is free software; you can redistribute it and/or modif…
阅读更多...
用通俗易懂的方式讲解：使用 Mistral-7B 和 Langchain 搭建基于PDF文件的聊天机器人

用通俗易懂的方式讲解：使用 Mistral-7B 和 Langchain 搭建基于PDF文件的聊天机器人

在本文中&#xff0c;使用LangChain、HuggingFaceEmbeddings和HuggingFace的Mistral-7B LLM创建一个简单的Python程序&#xff0c;可以从任何pdf文件中回答问题。 一、LangChain简介 LangChain是一个在语言模型之上开发上下文感知应用程序的框架。LangChain使用带prompt和few…
阅读更多...
最新文章

Copyright @ 2022~2023