hdu 1102 uva 10397(最小生成树prim)

2024-09-09 16:38
文章标签 最小 生成 hdu prim uva 1102 10397

本文主要是介绍hdu 1102 uva 10397(最小生成树prim),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

hdu 1102:

题意:

给一个邻接矩阵,给一些村庄间已经修的路,问最小生成树。


解析:

把已经修的路的权值改为0,套个prim()。

注意prim 最外层循坏为n-1。


代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int maxn = 100 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = 4 * atan(1.0);
const double ee = exp(1.0);int n;
int g[maxn][maxn];int prim()
{bool vis[maxn];int dis[maxn];memset(vis, false, sizeof(vis));memset(dis, inf, sizeof(dis));vis[1] = true;dis[1] = 0;int res = 0;int mark = 1;for (int i = 1; i <= n - 1; i++)///mark = 1 so n - 1{for (int j = 1; j <= n; j++){if (!vis[j] && g[mark][j] < dis[j])dis[j] = g[mark][j];}int mindis = inf;for (int j = 1; j <= n; j++){if (!vis[j] && dis[j] < mindis){mindis = dis[j];mark = j;}}vis[mark] = true;res += mindis;}return res;
}int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALwhile (~scanf("%d", &n)){for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){scanf("%d", &g[i][j]);}}int q;scanf("%d", &q);while (q--){int u, v;scanf("%d%d", &u, &v);g[u][v] = g[v][u] = 0;}printf("%d\n", prim());}return 0;
}

uva 10397:

基本上是一样的题目。。

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int maxn = 750 + 10;
const int inf = sqrt(2 * 20000 * 20000) + 10;int n;
double g[maxn][maxn];
double x[maxn], y[maxn];double dist(double x1, double y1, double x2, double y2)
{return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}double prim()
{double dis[maxn];bool vis[maxn];for (int i = 0; i <= n; i++){dis[i] = inf;vis[i] = false;}dis[1] = 0.0;vis[1] = true;double res = 0.0;int mark = 1;for (int i = 1; i <= n - 1; i++){for (int j = 1; j <= n; j++){if (!vis[j] && g[mark][j] < dis[j])dis[j] = g[mark][j];}double mindis = inf;for (int j = 1; j <= n; j++){if (!vis[j] && dis[j] < mindis){mindis = dis[j];mark = j;}}vis[mark] = true;res += mindis;}return res;
}int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALwhile (~scanf("%d", &n)){for (int i = 1; i <= n; i++){scanf("%lf%lf", &x[i], &y[i]);}for (int i = 1; i <= n; i++){for (int j = i + 1; j <= n; j++){g[i][j] = g[j][i] = dist(x[i], y[i], x[j], y[j]);}}int q;scanf("%d", &q);for (int i = 0; i < q; i++){int u, v;scanf("%d%d", &u, &v);g[u][v] = g[v][u] = 0;}
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 1; j <= n; j++)
//            {
//                printf("%.2lf ", g[i][j]);
//            }
//            printf("\n");
//        }printf("%.2lf\n", prim());}return 0;
}


这篇关于hdu 1102 uva 10397(最小生成树prim)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1151702

相关文章

Maven项目中集成数据库文档生成工具的操作步骤

《Maven项目中集成数据库文档生成工具的操作步骤》在Maven项目中,可以通过集成数据库文档生成工具来自动生成数据库文档,本文为大家整理了使用screw-maven-plugin(推荐)的完... 目录1. 添加插件配置到 pom.XML2. 配置数据库信息3. 执行生成命令4. 高级配置选项5. 注意事

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2

使用Python自动化生成PPT并结合LLM生成内容的代码解析

《使用Python自动化生成PPT并结合LLM生成内容的代码解析》PowerPoint是常用的文档工具,但手动设计和排版耗时耗力,本文将展示如何通过Python自动化提取PPT样式并生成新PPT,同时... 目录核心代码解析1. 提取 PPT 样式到 jsON关键步骤:代码片段:2. 应用 JSON 样式到

SpringBoot实现二维码生成的详细步骤与完整代码

《SpringBoot实现二维码生成的详细步骤与完整代码》如今,二维码的应用场景非常广泛,从支付到信息分享,二维码都扮演着重要角色,SpringBoot是一个非常流行的Java基于Spring框架的微... 目录一、环境搭建二、创建 Spring Boot 项目三、引入二维码生成依赖四、编写二维码生成代码五

Android与iOS设备MAC地址生成原理及Java实现详解

《Android与iOS设备MAC地址生成原理及Java实现详解》在无线网络通信中,MAC(MediaAccessControl)地址是设备的唯一网络标识符,本文主要介绍了Android与iOS设备M... 目录引言1. MAC地址基础1.1 MAC地址的组成1.2 MAC地址的分类2. android与I

PyQt5+Python-docx实现一键生成测试报告

《PyQt5+Python-docx实现一键生成测试报告》作为一名测试工程师,你是否经历过手动填写测试报告的痛苦,本文将用Python的PyQt5和python-docx库,打造一款测试报告一键生成工... 目录引言工具功能亮点工具设计思路1. 界面设计:PyQt5实现数据输入2. 文档生成:python-

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

Python如何自动生成环境依赖包requirements

《Python如何自动生成环境依赖包requirements》:本文主要介绍Python如何自动生成环境依赖包requirements问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录生成当前 python 环境 安装的所有依赖包1、命令2、常见问题只生成当前 项目 的所有依赖包1、

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

Java利用docx4j+Freemarker生成word文档

《Java利用docx4j+Freemarker生成word文档》这篇文章主要为大家详细介绍了Java如何利用docx4j+Freemarker生成word文档,文中的示例代码讲解详细,感兴趣的小伙伴... 目录技术方案maven依赖创建模板文件实现代码技术方案Java 1.8 + docx4j + Fr