一:问题
1.问题描述
雷雷承包了很多片麦田,为了灌溉这些麦田,雷雷在第一个麦田挖了一口很深的水井,所有的麦田都从这口井来引水灌溉。
为了灌溉,雷雷需要建立一些水渠,以连接水井和麦田,雷雷也可以利用部分麦田作为“中转站”,利用水渠连接不同的麦田,这样只要一片麦田能被灌溉,则与其连接的麦田也能被灌溉。
现在雷雷知道哪些麦田之间可以建设水渠和建设每个水渠所需要的费用(注意不是所有麦田之间都可以建立水渠)。请问灌溉所有麦田最少需要多少费用来修建水渠。
2.格式
输入格式
输入的第一行包含两个正整数n, m,分别表示麦田的片数和雷雷可以建立的水渠的数量。麦田使用1, 2, 3, ……依次标号。
接下来m行,每行包含三个整数ai, bi, ci,表示第ai片麦田与第bi片麦田之间可以建立一条水渠,所需要的费用为ci。
输出格式
输出一行,包含一个整数,表示灌溉所有麦田所需要的最小费用。
3.样例
样例输入
4 4
1 2 1
2 3 4
2 4 2
3 4 3
样例输出
6
样例说明
建立以下三条水渠:麦田1与麦田2、麦田2与麦田4、麦田4与麦田3。
4.评测用例规模与约定
前20%的评测用例满足:n≤5。
前40%的评测用例满足:n≤20。
前60%的评测用例满足:n≤100。
所有评测用例都满足:1≤n≤1000,1≤m≤100,000,1≤ci≤10,000。
二:理解
最小生成树
kruskal算法和prim算法
一.kruskal算法
1.数据结构:
struct Node {
int a;
int b;
int c; //花销
}; //存储渠道信息
vector<Node>p; //存储输入的渠道信息
int n, m;
int sign[1005]; //标志着某一麦田属于哪一类别。
2.将建立渠道的信息都存到vector中,然后针对花销进行排序
bool cmp(const Node s, const Node e)
{
return s.c < e.c; //按着耗资来排序
}
sort(p.begin(),p.end(),cmp);
3.kruskal算法
如果不属于同一类的话,那么这个渠道就需要建立,直接计算费用就可以。
后续的处理就是:将不同的一类归为一类。
for(int i=0; i<m; i++)
{
int x = sign[p[i].a];
int y = sign[p[i].b];
if(x != y) //不是一类
{
counts += p[i].c;
for(int j=1; j<=n; j++) //将不同类别的归为一类,
if(sign[j] == y)
sign[j] = x;
}
}
二:prim算法
①.模板式:
理解:
1.num[i][j] = c;记录渠道信息,表示麦田i和麦田j建立渠道,花费c
注意: num[i][j] = num[j][i] = c;(无向)
fill(num[0],num[1004]+1005,inf);
loop(i,0,m)
{
int a, b, c;
cin >> a >> b >> c;
num[a][b] = c;
num[b][a] = c;
}
2.初始化第一个点
sign[i] 记录 从1点开始到第i点的花销。
sign[1] = -1;
loop(i, 2, n+1) //保存和1有关系的边
sign[i] = num[1][i];
3.判断哪个是最少的花销,并且将这个点置为B类。
loop(j, 2, n+1) //找和判断的这个点联系最小的边
{
if(sign[j]!=-1 && sign[j]<minnum)
{
minnum = sign[j];
temp = j;
}
}
sum += minnum; //把合适的边加起来
sign[temp] = -1; //并且标记指向的这个点不能再寻找
4.继续从找到的那个点出发,更新sign的值
loop(j, 2, n+1) //更新权值
if(sign[j]!=-1 && sign[j]>num[temp][j])
sign[j] = num[temp][j];
注:
感觉这个不是真的prim算法,原因:
在找到最小的边,将对应的点记录下来,只是直接对这个点进行扩展(应该是对于整个遍历过得点进行扩展)。
例如:
一共5个点,其中1,2两个点已经加入到另一类B类(遍历过的一类),那么A类就还剩3,4,5三个点。在进行扩展的时候,我们就看从1点或者2点出发(终点不能是这两个点)的边,哪一个权值最小。就在继续记录这个边,将对应的点加入A类。以此类推…
我改了一下代码:
(这个是超时的)
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 0x7f7f7f7f
#define loop(i,start,end) for(int i=start; i<end; i++)
//记录渠道信息,num[i][j] = c;表示麦田i和麦田j建立渠道,花费c
int num[1005][1005];
//sign[i] = c;表示指向麦田i的渠道,花费c。
//为-1时表示,已经判断过指向i的渠道(边)
int sign[1005];
int n, m;
int prim()
{
int sum = 0;
sign[1] = -1;
loop(i, 2, n+1) //保存和1有关系的边
sign[i] = num[1][i];
loop(i,0,n-1) //找n-1个边
{
int minnum = inf;
int temp;
loop(j, 2, n+1) //找和判断的这个点联系最小的边
{
if(sign[j]!=-1 && sign[j]<minnum)
{
minnum = sign[j];
temp = j;
}
}
sum += minnum; //把合适的边加起来
sign[temp] = -1; //并且标记指向的这个点不能再寻找
loop(k,1,n+1)
{
if(sign[k] == -1) //在B类里面
{
loop(j, 2, n+1) //更新权值
if(sign[j]!=-1 && sign[j]>num[k][j])
sign[j] = num[k][j];
}
}
}
return sum;
}
int main()
{
cin >> n >> m;
fill(num[0],num[1004]+1005,inf);
loop(i,0,m)
{
int a, b, c;
cin >> a >> b >> c;
num[a][b] = c;
num[b][a] = c;
}
cout << prim();
return 0;
}
②.优先队列式:
优点就是不用判断大小,优先队列不是普通的队列,是优先级高的先输出。
1.数据结构
vector数组+优先队列
struct Node {
int to;
int c;
//优先队列,从小到大
friend bool operator <(Node a, Node b)
{
return a.c > b.c;
}
};
vector<Node> node[1005]; //没用二维数组
priority_queue<Node> p;
int vis[1005] = {
0};
int n,m;
注意这个优先队列需要有这一句话:
friend bool operator <(Node a, Node b)
{
return a.c > b.c; //由小到大
}
2.初始化vector,初始化优先队列
for(int i=0; i<m; ++i)
{
int a,b,c;
cin >> a >> b >> c;
node[a].push_back(Node{
b, c});
node[b].push_back(Node{
a, c});
}
for(int i=0; i<node[1].size(); ++i)
p.push(node[1][i]);
vis[1] = 1;
3.由选中的边扩展边
Node temp = p.top(); //最小的那个
p.pop();
int i = temp.to;
if(vis[i])
continue; //如果已经访问过了,需要跳过,否则构成回路了
vis[i] = 1;
for(int j=0; j<node[i].size(); j++)
{
if(!vis[node[i][j].to]) //将连接没有访问过的点的边加入优先队列
p.push(node[i][j]);
}
注:这个思路比较好理解,就是按照prim算法的思路来的。
由优先队列加持。
开始就将由与1点连接的边加入队列,选中最小的边,按着这个边的终点假如是2继续扩展边。将对应的边也都入队,这时候队列里面的边是与1或2有连接的边然后在从这些边里面找最小的边。依次类推…,就会找到最优的路,并且,有visited[i]来判断是否遍历过,遍历过的就不考虑。
总注:
1.->介绍sort()排序<-
升序:sort(begin,end,less<data-type>());
降序:sort(begin,end,greater<data-type>()).
2.介绍kruskal算法
->kruskal算法<-
3:介绍prim算法
->prim算法<-
4.fill()函数
fill()函数参数:fill(first,last,val);
// first 为容器的首迭代器,last为容器的末迭代器,val为将要替换的值。
注意:
fill()中 ,它的原理是把那一块单元赋成指定的值,也就是说任何值都可以
memset(),则是将s所指向的某一块内存中的每个字节的内容全部设置为ch指定的ASCII值,即0 、1
5.介绍优先队列
->队列与优先队列<-
三:代码
kruskal代码:
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct Node {
int a;
int b;
int c;
};
//Node ps[100,005];
vector<Node>p;
int n, m;
int sign[1005];
bool cmp(const Node s, const Node e)
{
return s.c < e.c; //按着耗资来排序
}
int Kruskal()
{
long long counts = 0;
for(int i=1; i<=n; i++)
sign[i] = i;
for(int i=0; i<m; i++)
{
int x = sign[p[i].a];
int y = sign[p[i].b];
if(x != y) //不是一类
{
counts += p[i].c;
for(int j=1; j<=n; j++) //将不同类别的归为一类,
if(sign[j] == y)
sign[j] = x;
}
}
return counts;
}
int main()
{
Node temp;
cin >> n >> m;
for(int i=0; i<m; i++)
{
cin >> temp.a >> temp.b >> temp.c;
p.push_back(temp);
}
sort(p.begin(),p.end(),cmp);
cout << Kruskal();
return 0;
}
prim算法代码:
模板式:
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 0x7f7f7f7f
#define loop(i,start,end) for(int i=start; i<end; i++)
//记录渠道信息,num[i][j] = c;表示麦田i和麦田j建立渠道,花费c
int num[1005][1005];
//sign[i] = c;表示指向麦田i的渠道,花费c。
//为-1时表示,已经判断过指向i的渠道(边)
int sign[1005];
int n, m;
int prim()
{
int sum = 0;
sign[1] = -1;
loop(i, 2, n+1) //保存和1有关系的边
sign[i] = num[1][i];
loop(i,0,n-1) //找n-1个边
{
int minnum = inf;
int temp;
loop(j, 2, n+1) //找和判断的这个点联系最小的边
{
if(sign[j]!=-1 && sign[j]<minnum)
{
minnum = sign[j];
temp = j;
}
}
sum += minnum; //把合适的边加起来
sign[temp] = -1; //并且标记指向的这个点不能再寻找
loop(j, 2, n+1) //更新权值
if(sign[j]!=-1 && sign[j]>num[temp][j])
sign[j] = num[temp][j];
}
return sum;
}
int main()
{
cin >> n >> m;
fill(num[0],num[1004]+1005,inf);
loop(i,0,m)
{
int a, b, c;
cin >> a >> b >> c;
num[a][b] = c;
num[b][a] = c;
}
cout << prim();
return 0;
}
优先队列式:
#include<bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct Node {
int to;
int c;
//优先队列,从小到大
friend bool operator <(Node a, Node b)
{
return a.c > b.c;
}
};
vector<Node> node[1005];
priority_queue<Node> p;
int vis[1005] = {
0};
int n,m;
int prim()
{
for(int i=0; i<node[1].size(); ++i)
p.push(node[1][i]);
vis[1] = 1;
int num = 0, counts = 0;
while(!p.empty())
{
Node temp = p.top();
p.pop();
int i = temp.to;
if(vis[i])
continue; //如果已经访问过了,需要跳过,否则构成回路了
vis[i] = 1;
for(int j=0; j<node[i].size(); j++)
{
if(!vis[node[i][j].to]) //将连接没有访问过的点的边加入优先队列
p.push(node[i][j]);
}
counts += temp.c;
num++;
if(num==n-1)
return counts; //n个点的图,n-1条边就是连通图,退出
}
}
int main()
{
cin>>n>>m;
for(int i=0; i<m; ++i)
{
int a,b,c;
cin >> a >> b >> c;
node[a].push_back(Node{
b, c});
node[b].push_back(Node{
a, c});
}
cout<<prim();
return 0;
}
文章浏览阅读1.6w次,点赞8次,收藏41次。生活中我们无时不刻不都要在网站搜索资源,但就是缺少一个趁手的资源搜索网站,如果有一个比较好的资源搜索网站可以帮助我们节省一大半时间!今天小编在这里为大家分享5款超厉害的资源搜索网站,每一款都可以让你的资源丰富精彩!网盘传奇一款最有效的网盘资源搜索网站你还在为找网站里面的资源而烦恼找不到什么合适的工具而烦恼吗?这款网站传奇网站汇聚了4853w个资源,并且它每一天都会持续更新资源;..._最全资源搜索引擎
文章浏览阅读4.5k次,点赞5次,收藏18次。阅读测试程序,设计一个Book类。函数接口定义:class Book{}该类有 四个私有属性 分别是 书籍名称、 价格、 作者、 出版年份,以及相应的set 与get方法;该类有一个含有四个参数的构造方法,这四个参数依次是 书籍名称、 价格、 作者、 出版年份 。裁判测试程序样例:import java.util.*;public class Main { public static void main(String[] args) { List <Book>_6-1 book类的设计java
文章浏览阅读613次,点赞28次,收藏27次。相比于以前的传统手工管理方式,智能化的管理方式可以大幅降低学校的运营人员成本,实现了校园导航的标准化、制度化、程序化的管理,有效地防止了校园导航的随意管理,提高了信息的处理速度和精确度,能够及时、准确地查询和修正建筑速看等信息。课题主要采用微信小程序、SpringBoot架构技术,前端以小程序页面呈现给学生,结合后台java语言使页面更加完善,后台使用MySQL数据库进行数据存储。微信小程序主要包括学生信息、校园简介、建筑速看、系统信息等功能,从而实现智能化的管理方式,提高工作效率。
传统上用户登陆状态会以 Session 的形式保存在服务器上,而 Session ID 则保存在前端的 Cookie 中;而使用 JWT 以后,用户的认证信息将会以 Token 的形式保存在前端,服务器不需要保存任何的用户状态,这也就是为什么 JWT 被称为无状态登陆的原因,无状态登陆最大的优势就是完美支持分布式部署,可以使用一个 Token 发送给不同的服务器,而所有的服务器都会返回同样的结果。有状态和无状态最大的区别就是服务端会不会保存客户端的信息。
文章浏览阅读784次。发表于10小时前| 2674次阅读| 来源TechCrunch| 19 条评论| 作者Jon EvansiOSAndroid应用开发产品编程语言JavaObjective-C摘要:即便Android市场份额已经超过80%,对于开发者来说,使用哪一个平台做开发仍然很难选择。本文从开发环境、配置、UX设计、语言、API、网络、分享、碎片化、发布等九个方面把Android和iOS_ios 开发角度
搜索引擎的发展历史可以追溯到20世纪90年代初,随着互联网的快速发展和信息量的急剧增加,人们开始感受到了获取和管理信息的挑战。这些阶段展示了搜索引擎在技术和商业模式上的不断演进,以满足用户对信息获取的不断增长的需求。
文章浏览阅读990次。对象特性是指控制对象的输出参数和输入参数之间的相互作用规律。放大系数K描述控制对象特性的静态特性参数。它的意义是:输出量的变化量和输入量的变化量之比。时间常数T当输入量发生变化后,所引起输出量变化的快慢。(动态参数) ..._控制对象特性
文章浏览阅读5.7w次,点赞50次,收藏276次。FRP搭建内网穿透1.概述:frp可以通过有公网IP的的服务器将内网的主机暴露给互联网,从而实现通过外网能直接访问到内网主机;frp有服务端和客户端,服务端需要装在有公网ip的服务器上,客户端装在内网主机上。2.简单的图解:3.准备工作:1.一个域名(www.test.xyz)2.一台有公网IP的服务器(阿里云、腾讯云等都行)3.一台内网主机4.下载frp,选择适合的版本下载解压如下:我这里服务器端和客户端都放在了/usr/local/frp/目录下4.执行命令# 服务器端给执_locyanfrp
文章浏览阅读687次。题目:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=93745#problem/A题意:给出r*c的01矩阵,可以翻转格子使得0表成1,1变成0,求出最小的步数使得每一行中1的个数相等,每一列中1的个数相等。思路:网络流。容量可以保证每一行和每一列的1的个数相等,费用可以算出最小步数。行向列建边,如果该格子是_uva12534
文章浏览阅读504次。1、Let's Encrypt 90天,支持泛域名2、Buypass:https://www.buypass.com/ssl/resources/go-ssl-technical-specification6个月,单域名3、AlwaysOnSLL:https://alwaysonssl.com/ 1年,单域名 可参考蜗牛(wn789)4、TrustAsia5、Alpha..._csdn alphassl免费申请
文章浏览阅读1.6k次。测试算法的性能 很多时候我们需要对算法的性能进行测试,最简单的方式是看算法在特定的数据集上的执行时间,简单的测试算法性能的函数实现见testSort()。【思想】:用clock_t计算某排序算法所需的时间,(endTime - startTime)/ CLOCKS_PER_SEC来表示执行了多少秒。【关于宏CLOCKS_PER_SEC】:以下摘自百度百科,“CLOCKS_PE_算法性能测试
文章浏览阅读1.2k次。fromhttps://towardsdatascience.com/finding-lane-lines-simple-pipeline-for-lane-detection-d02b62e7572bIdentifying lanes of the road is very common task that human driver performs. This is important ..._lanedetectionlite