POJ1258 Agri-Net MST最小生成树题解
Net 生成 最小 题解 MST
2023-09-11 14:15:00 时间
搭建一个最小代价的网络,最原始的最小生成树的应用。
这里使用Union find和Kruskal算法求解.
注意:
1 给出的数据是原始的矩阵图,可是须要转化为边表示的图,方便运用Kruskal,由于须要sort
2 降低边。一个矩阵最多须要(N*N-N)>>1条边,有人讨论本题是否有向,那是无意义的。由于本题的最小生成树和方向无关。
3 使用Union find是为了推断是否有环。比原始推断快非常多。
#include <stdio.h> #include <stdlib.h> const int MAX_VEC = 101; int N; //number of vertices struct SubSet { int p, rank; }; struct Edge { int src, des, wei; }; struct Graph { int V, E; Edge *edge; Graph(int v, int e) : V(v), E(e) { edge = new Edge[E]; } ~Graph() { if (edge) delete[]edge; edge = NULL; } }; static int cmp(const void *a, const void *b) { Edge *a1 = (Edge *) a; Edge *b1 = (Edge *) b; return a1->wei - b1->wei; } SubSet *subs; Edge *res; Graph *gra; void initResource() { subs = new SubSet[N]; for (int i = 0; i < N; i++) { subs[i].p = i; subs[i].rank = 0; } res = new Edge[N-1]; } inline void releaseResource() { if (subs) delete [] subs; if (res) delete [] res; } int find(int node) { if (subs[node].p != node) subs[node].p = find(subs[node].p); return subs[node].p; } inline void unionTwo(int x, int y) { int xroot = find(x); int yroot = find(y); if (subs[xroot].rank < subs[yroot].rank) subs[xroot].p = yroot; else if (subs[xroot].rank > subs[yroot].rank) subs[yroot].p = xroot; else { subs[xroot].rank++; subs[yroot].p = xroot; } } int mst() { initResource(); qsort(gra->edge, gra->E, sizeof(Edge), cmp); for (int i = 0, v = 0; i < gra->E && v < gra->V - 1; i++) { int xroot = find(gra->edge[i].src); int yroot = find(gra->edge[i].des); if (xroot != yroot) { unionTwo(xroot, yroot); res[v++] = gra->edge[i]; } } int ans = 0; for (int i = 0; i < N-1; i++) { ans += res[i].wei; } releaseResource(); return ans; } int main() { int w; while (~scanf("%d", &N)) { gra = new Graph(N, (N*N-N)>>1); int e = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { scanf("%d", &w); if (j <= i) continue; //下三角形的值不入边 gra->edge[e].src = i; gra->edge[e].des = j; gra->edge[e++].wei = w; } } printf("%d\n", mst()); delete gra; } return 0; }
相关文章
- Asp.Net Core WebApi6解决跨域问题
- Building Websites in ASP.NET
- jmeter压测报java.net.SocketException: Connection reset
- 高并发分布式系统中生成全局唯一(订单号)Id js返回上一页并刷新、返回上一页、自动刷新页面 父页面操作嵌套iframe子页面的HTML标签元素 .net判断System.Data.DataRow中是否包含某列 .Net使用system.Security.Cryptography.RNGCryptoServiceProvider类与System.Random类生成随机数
- ASP.NET Core 2.2 : 十六.扒一扒新的Endpoint路由方案 try.dot.net 的正确使用姿势 .Net NPOI 根据excel模板导出excel、直接生成excel .Net NPOI 上传excel文件、提交后台获取excel里的数据
- 中小研发团队架构实践之生产环境诊断工具WinDbg 三分钟学会.NET微服务之Polly 使用.Net Core+IView+Vue集成上传图片功能 Fiddler原理~知多少? ABP框架(asp.net core 2.X+Vue)模板项目学习之路(一) C#程序中设置全局代理(Global Proxy) WCF 4.0 使用说明 如何在IIS上发布,并能正常访问
- List多个字段标识过滤 IIS发布.net core mvc web站点 ASP.NET Core 实战:构建带有版本控制的 API 接口 ASP.NET Core 实战:使用 ASP.NET Core Web API 和 Vue.js 搭建前后端分离项目 Using AutoFac
- .net mvc 站点自带简易SSL加密传输 Word报告自动生成(例如 导出数据库结构) 微信小程序:动画(Animation) SignalR 设计理念(一) ASP.NET -- WebForm -- ViewState ASP.NET -- 一般处理程序ashx 常用到的一些js方法,记录一下 CryptoJS与C#AES加解密互转
- 百度地图和高德地图坐标系的互相转换 四种Sandcastle方法生成c#.net帮助类帮助文档 文档API生成神器SandCastle使用心得 ASP.NET Core
- 【转】.NET(C#):浅谈程序集清单资源和RESX资源 关于单元测试的思考--Asp.Net Core单元测试最佳实践 封装自己的dapper lambda扩展-设计篇 编写自己的dapper lambda扩展-使用篇 正确理解CAP定理 Quartz.NET的使用(附源码) 整理自己的.net工具库 GC的前世与今生 Visual Studio Package 插件开发之自动生
- C#字符串数组排序 C#排序算法大全 C#字符串比较方法 一个.NET通用JSON解析/构建类的实现(c#) C#处理Json文件 asp.net使用Jquery+iframe传值问题
- C#编译器优化那点事 c# 如果一个对象的值为null,那么它调用扩展方法时为甚么不报错 webAPI 控制器(Controller)太多怎么办? .NET MVC项目设置包含Areas中的页面为默认启动页 (五)Net Core使用静态文件 学习ASP.NET Core Razor 编程系列八——并发处理
- 使用 C#/.NET Core 实现单体设计模式
- Net is as typeof 运行运算符详解 net 自定义泛型那点事
- .NET版Word处理控件Aspose.Words功能演示:从C#.NET中的模板生成Word文档
- c# ASP.NET怎么看EF生成的SQL语句和EF执行的所有活动
- POJ 1258 Agri-Net (最小生成树+Prim)
- 使用批处理根据项目工程文件生成Nuget包并发布(支持.NET Core)
- Magicodes.WeiChat——ASP.NET Scaffolding生成增删改查、分页、搜索、删除确认、批量操作、批量删除等业务代码
- jmeter 运行脚本报错 java.net.BindException: Address already in use
- 《精通 ASP.NET MVC 4》----第 2 章 第一个MVC应用程序 2.1 准备工作站
- ASP.NET Core WebApi使用Swagger生成API说明文档【特性版】
- C#/WPF/.NET 找到的程序集清单定义与程序集引用不匹配
- asp.net 后端验证
- .NET Core跨平台:使用.NET Core开发一个初心源商城总括
- 关于 ASP.NET MVC 中的视图生成
- Asp.net web form 动态生成控件的注意事项
- 【C#/WPF】.Net生成二维码QRCode的工具
- C#与.NET Framework c#编程语言,和java是一样的。(c#,java) -->javaweb,asp.net