(JZ4252)2019.01.30【NOIP提高组】模拟B组 0.QYQ的图

2024-01-30 05:48

本文主要是介绍(JZ4252)2019.01.30【NOIP提高组】模拟B组 0.QYQ的图,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【五校联考7day2】QYQ的图

Description

给你一个n个点,m条边的无向图,每个点有一个非负的权值ci,现在你需要选择一些点,使得每一个点都满足:
如果这个点没有被选择,则与它有边相连的所有点都必须被选择。
问:满足上述条件的点集中,所有选择的点的权值和最小是多少?
QYQ很快就解决了这个问题,但是他已经回到了左下角……没有留下答案,现在只好请你来解决这个问题啦!

Input

从文件graph.in中输入数据。
输入的第一行包含两个整数n,m
输入的第二行包含n个整数,其中第i个整数代表ci
输入的第三行到第m+2行,每行包含两个整数u,v,代表点u和点v之间有一条边

Output

输出到文件graph.out中。
输出的第一行包含一个整数,代表最小的权值和

Sample Input
3 1
1 2 3
3 1

Sample Output
1
样例说明:
只选择1号点,满足题意

Data Constraint

对于20% 的数据:n<=10
对于40%的数据:n<=20
对于100%的数据:1<=n<=50, 1<=m<=500, 0<=c<=1000
图中可能会有重边,自环。
点的编号为1—n。

纪中题解:

直接搜索就好了,当然不要 O(2^n)那种,每次搜索的时候如果这个点不选,就直接把与它相连的所有点选上,搜索的时候加入一些剪枝,比如如果现在的结果已经比现在的最佳答案大了就直接不搜了

悲催的故事:

   原本是想直接打个暴搜,dfs选的点。那么就反推题目(如果这个点没有被选择,则与它有边相连的所有点都必须被选择):如果这个点被选择,则与它有边相连的所有点都不被选择。因为这样代价最小。
   过了水样例,但后来发现,如下图:肯定要选权值为二的那个点,但如果按之前的方法来算,那么3–10就会选10,3–5就选不了了
画得丑不要介意
   然后就想着dfs不选的数。每不选一个数,就将与它有边相连的点加上。我们设k数组来装可以dfs的点,不可以的点包括:之前dfs过的点,加上的点。然后再dfs。
   不过不知道是回溯出了问题还是怎么的,只有20分╮(╯▽╰)╭(不过你也没有判断自环和重边啊!(○・`Д´・ ○))

20%:

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,ans=233333,minn;
int c[55];
bool p[55][55],d[55][55],k[55];void dfs(int x){
bool e[55][55];k[x]=0;if (minn>=ans) return;memcpy(e,p,sizeof(p));for (int i=1; i<=n; i++) if (p[x][i]){minn+=c[i];k[i]=0; p[x][i]=0; p[i][x]=0;for (int j=1; j<=n; j++) {p[i][j]=0; p[j][i]=0;}}for (int i=1; i<=n; i++) if (k[i]) dfs(i); memcpy(p,e,sizeof(e));k[x]=1;
}
int main(){freopen("graph.in","r",stdin);freopen("graph.out","w",stdout);scanf("%d%d",&n,&m);for (int i=1; i<=n; i++) scanf("%d",&c[i]);for (int i=1; i<=m; i++){int u,v;scanf("%d%d",&u,&v);p[u][v]=1; p[v][u]=1;}memcpy(d,p,sizeof(d));for (int i=1; i<=n; i++) {minn=0;memcpy(p,d,sizeof(p)); memset(k,1,sizeof(k));dfs(i);ans=min(ans,minn);}printf("%d",ans);return 0;fclose(stdin); fclose(stdout);
}

   
   
   

100%

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{int to,next;
}a[1100];
int n,m,tot,ans,minn;
int b[55],c[55],ls[55],jh[55];
bool k[55],bj[55];void add(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;
}void dfs(int x){b[++tot]=x; k[x]=1;for (int i=ls[x]; i; i=a[i].next)if (!k[a[i].to]) dfs(a[i].to);
}
void QYQ(int dep,int z){if(z>=minn) return;//剪枝if(dep>tot){minn=min(minn,z);return;}QYQ(dep+1,z+c[b[dep]]);if(!jh[b[dep]]&&!bj[b[dep]]){for(int i=ls[b[dep]]; i; i=a[i].next) jh[a[i].to]++;QYQ(dep+1,z);for(int i=ls[b[dep]]; i; i=a[i].next) jh[a[i].to]--;}
}
int main(){freopen("graph.in","r",stdin);freopen("graph.out","w",stdout);scanf("%d%d",&n,&m);for (int i=1; i<=n; i++) scanf("%d",&c[i]);for (int i=1; i<=m; i++){int u,v;scanf("%d%d",&u,&v);add(u,v); add(v,u);if (u==v) bj[u]=1;}for (int i=1; i<=n; i++) {minn=233333333; tot=0;if (k[i]) continue;dfs(i);QYQ(1,0);ans+=minn;}printf("%d",ans);return 0;fclose(stdin); fclose(stdout);
}

这篇关于(JZ4252)2019.01.30【NOIP提高组】模拟B组 0.QYQ的图的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

30常用 Maven 命令

Maven 是一个强大的项目管理和构建工具,它广泛用于 Java 项目的依赖管理、构建流程和插件集成。Maven 的命令行工具提供了大量的命令来帮助开发人员管理项目的生命周期、依赖和插件。以下是 常用 Maven 命令的使用场景及其详细解释。 1. mvn clean 使用场景:清理项目的生成目录,通常用于删除项目中自动生成的文件(如 target/ 目录)。共性规律:清理操作

2024网安周今日开幕,亚信安全亮相30城

2024年国家网络安全宣传周今天在广州拉开帷幕。今年网安周继续以“网络安全为人民,网络安全靠人民”为主题。2024年国家网络安全宣传周涵盖了1场开幕式、1场高峰论坛、5个重要活动、15场分论坛/座谈会/闭门会、6个主题日活动和网络安全“六进”活动。亚信安全出席2024年国家网络安全宣传周开幕式和主论坛,并将通过线下宣讲、创意科普、成果展示等多种形式,让广大民众看得懂、记得住安全知识,同时还

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti

键盘快捷键:提高工作效率与电脑操作的利器

键盘快捷键:提高工作效率与电脑操作的利器 在数字化时代,键盘快捷键成为了提高工作效率和优化电脑操作的重要工具。无论是日常办公、图像编辑、编程开发,还是游戏娱乐,掌握键盘快捷键都能带来极大的便利。本文将详细介绍键盘快捷键的概念、重要性、以及在不同应用场景中的具体应用。 什么是键盘快捷键? 键盘快捷键,也称为热键或快捷键,是指通过按下键盘上的一组键来完成特定命令或操作的方式。这些快捷键通常涉及同

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

如何提高 GitHub 的下载速度

如何提高 GitHub 的下载速度 文章目录 如何提高 GitHub 的下载速度1. 注册账号2. 准备好链接3. 创建仓库4. 在码云上下载代码5. 仓库更新了怎么办 一般来说,国内的朋友从 GitHub 上面下载代码,速度最大是 20KB/s,这种龟速,谁能忍受呢? 本文介绍一种方法——利用“码云”,可以大大提高下载速度,亲测有效。 1. 注册账号 去“码云”注册一

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数