畅通工程
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 24323 Accepted Submission(s): 10621
行对应村庄间道路的成本,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间道路的成本(也是正整数)。为简单起见,村庄从1到M编号。当N为0时,全部输入结束,相应的结果不要输出。
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100
?
先引用百度百科
先构造一个只含 n 个顶点、而边集为空的子图,把子图中各个顶点看成各棵树上的根结点,之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,即把两棵树合成一棵树,反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直到森林中只有一棵树,也即子图中含有
n-1 条边为止。
最后一句很重要,停止条件是子图中含有n-1条边为止。
还有就是选取每一条边的时候要看看是否能与之前已选中的构成回路,不构成回路则选择一条距离最短的,若能构成回路则舍弃。
嗯这题无聊玩了一下操作符重载(刚开始写反了输出的结果比较大。),比较有意思的。鉴于sort的复杂度不大两者应该没啥差别,就是不用vector的情况下空间可以节省一点……没错我就是这么无聊= =
sort写法:
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define MM(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long LL;
const int N=1010;
struct info
{
int a;
int b;
int val;
info(){a=b=val=0;}
}; info G[3*N];
int vis[N]; void init()
{
MM(G);
for (int i=0; i<N; i++)
vis[i]=i;
}
bool cmp(const info &a,const info &b)
{
return a.val<b.val;
}
inline int find(int a)
{
if(vis[a]!=a)
return vis[a]=find(vis[a]);
return vis[a];
}
inline int merge(const int &a,const int &b)
{
int aa=find(a),bb=find(b);
if(aa!=bb)
{
vis[bb]=aa;
return 1;
}
return 0;
} int main(void)
{
int tcase,i,x,y,val,n,m;
scanf("%d",&tcase);
while (tcase--)
{
scanf("%d%d",&n,&m);
init();
int ans=0,cnt=0;
for (i=1; i<=m; i++)
{
scanf("%d%d%d",&G[i].a,&G[i].b,&G[i].val);
}
sort(G+1,G+m+1,cmp);
for (i=1; i<=m; i++)
{
if(cnt==n-1)
break;
if(merge(G[i].a,G[i].b))
{
cnt++;
ans+=G[i].val;
}
}
cnt==n-1?printf("%d\n",ans):puts("-1");
}
return 0;
}
优先队列写法:
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define MM(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long LL;
const int N=1010; struct info
{
int a;
int b;
int val;
bool operator<(const info &b) const
{
return val>b.val;
}
}; info G;
int vis[N];
priority_queue<info> Q; void debug(priority_queue<info> q)
{
while (!q.empty())
{
cout<<q.top().a<<" "<<q.top().b<<endl;
q.pop();
}
} void init()
{
for (int i=0; i<N; i++)
{
vis[i]=i;
}
while (!Q.empty())
Q.pop();
}
inline int find(int a)
{
if(vis[a]!=a)
return vis[a]=find(vis[a]);
return vis[a];
}
inline bool merge(int a,int b)
{
int aa=find(a),bb=find(b);
if(aa!=bb)
{
vis[bb]=aa;
return true;
}
return false;
}
int main(void)
{
int tcase,i,j,x,y,val,n,m;
scanf("%d",&tcase);
while (tcase--)
{
scanf("%d%d",&n,&m);
init();
int ans=0,cnt=0;
for (i=0; i<m; i++)
{
scanf("%d%d%d",&G.a,&G.b,&G.val);
Q.push(G);
}
//debug(Q);
while (!Q.empty())
{
info t=Q.top();
Q.pop();
if(cnt==n-1)
break;
if(merge(t.a,t.b))
{
cnt++;
ans+=t.val;
}
}
cnt==n-1?printf("%d\n",ans):puts("-1");
}
return 0;
}
ACM程序设计选修课——Problem E:(ds:图)公路村村通(优先队列或sort+克鲁斯卡尔+并查集优化)的更多相关文章
-
ACM程序设计选修课——Problem E:(ds:图)公路村村通(Prim)
问题 E: (ds:图)公路村村通 时间限制: 1 Sec 内存限制: 128 MB 提交: 9 解决: 5 题目描述 现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本, ...
-
ACM程序设计选修课——Problem F:(ds:图)旅游规划(优先队列+SPFA)
问题 F: (ds:图)旅游规划 时间限制: 1 Sec 内存限制: 128 MB 提交: 14 解决: 4 题目描述 有了一张自驾旅游路线图,你会知道城市间的高速公路长度.以及该公路要收取的过路 ...
-
ACM程序设计选修课——Problem D: (ds:树)合并果子(最优二叉树赫夫曼算法)
Problem D: (ds:树)合并果子 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 80 Solved: 4 [Submit][Status][ ...
-
pta08-图7 公路村村通 (30分)
08-图7 公路村村通 (30分) 现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本. 输入格式: 输入数据包括城镇数目正整数N ...
-
pat06-图6. 公路村村通(30)
06-图6. 公路村村通(30) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 现有村落间道路的统计数据表中,列出了有可能建设成标准公路的 ...
-
7-6 公路村村通(30 分) 【prime】
7-6 公路村村通(30 分) 现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本. 输入格式: 输入数据包括城镇数目正整数N(≤10 ...
-
7-10 公路村村通(30 分)(最小生成树Prim算法)
7-10 公路村村通(30 分) 现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本. 输入格式: 输入数据包括城镇数目正整数N(≤1 ...
-
PTA 7-1 公路村村通 (30分)
PTA 7-1 公路村村通 (30分) 现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本. 输入格式: 输入数据包括城镇数目正整数N ...
-
PTA 08-图7 公路村村通 (30分)
现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本. 输入格式: 输入数据包括城镇数目正整数NN(\le 1000≤1000)和候选道 ...
随机推荐
-
sharepoint 开发相关工具总结
1.CAML Designer 2013 开发caml用 http://biwug-web.sharepoint.com/SitePages/Caml_designer.aspx 2.SharePoi ...
-
Web 安全测试
http://blog.sina.com.cn/s/blog_a1bbddc70101dt12.html http://blog.csdn.net/pdn2000/article/details/64 ...
-
防止vuejs在解析时出现闪烁
---## 防止vuejs在解析时出现闪烁 ## 原因: 在使用vuejs.angularjs开发时,经常会遇见在如Chrome这类能够快速解析的浏览器上出现表达式({{ express }} ),或 ...
-
Zabbix 配置监控主机
1.新建主机: zabbix中的主机(Host)是要监控的网络实体(物理的,或者虚拟的);zabbix中,对于主机的定义非常灵活,它可以时一台物理服务器,一个网络交换机,一个虚拟机或者一些应用 zab ...
-
android中volley通信框架简介
1. 什么是Volley? 在这之前,我们在程序中需要和网络通信的时候,大体使用的东西莫过于AsyncTaskLoader,HttpURLConnection,AsyncTask,HTTPClient ...
-
清华大学iCenter区块链公开课 第二节
1.比特币区块的结构 比特币区块结构: 区块大小 区块头 辕老师简版区块: 2.比特币交易结构 输入(可以有多个):比特币来源的UTXO 输出(可以有多个):手续费.接收比特币的地址 总量.锁定脚本尺 ...
-
MUI音乐播放html5+audio模块
html5+ audio 模块MUI播放音频 Audio模块用于提供音频的录制和播放功能,可调用系统的麦克风设备进行录音操作,也可调用系统的扬声器设备播放音频文件.通过plus.audio获取音频管理 ...
-
Spring boot 集成 mybaits plus(代码生成器)
源码地址:https://github.com/YANGKANG01/Spring-Boot-Demo 代码生成操作 在pom.xml文件中引入以下包: <!-- mybatisplus与spr ...
-
vSphere SDK for Java 示例
示例代码: package com.vmware.event.connect; import java.net.MalformedURLException; import java.net.URL; ...
-
StringsUtil字符串工具类---灵活截取
package com.js.ai.modules.pointwall.interfac; import javax.print.attribute.standard.MediaName; publi ...