POJ——T2421 Constructing Roads
2024-08-31 12:10:43
http://poj.org/problem?id=2421
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 24132 | Accepted: 10368 |
Description
There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected.
We know that there are already some roads between some villages and your job is the build some roads such that all the villages are connect and the length of all the roads built is minimum.
Input
The first line is an integer N (3 <= N <= 100), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 1000]) between village i and village j.
Then there is an integer Q (0 <= Q <= N * (N + 1) / 2). Then come Q lines, each line contains two integers a and b (1 <= a < b <= N), which means the road between village a and village b has been built.
Output
You should output a line contains an integer, which is the length of all the roads to be built such that all the villages are connected, and this value is minimum.
Sample Input
3
0 990 692
990 0 179
692 179 0
1
1 2
Sample Output
179
Source
PKU Monthly,kicc
把已经修好的路得代价改成0,再跑最小生成树就可以了。
#include <algorithm>
#include <cstdio> using namespace std; const int N();
int n,q,u,v,w;
int dis[N][N],ans;
int minn,vis[N],d[N]; void Prime()
{
for(int i=;i<=n;i++) d[i]=dis[][i];
d[]=vis[]=;
for(int i=;i<n;i++)
{
minn=;
for(int j=;j<=n;j++)
if(!vis[j]&&(!minn||d[j]<d[minn])) minn=j;
vis[minn]=;
for(int j=;j<=n;j++)
if(!vis[j]) d[j]=min(d[j],dis[minn][j]);
}
for(int i=;i<=n;i++) ans+=d[i];
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&dis[i][j]);
scanf("%d",&q);
for(;q;q--)
{
scanf("%d%d",&u,&v);
dis[u][v]=dis[v][u]=;
}
Prime();
printf("%d",ans);
return ;
}
最新文章
- Django 1.10 中文文档------3.3.8 会话sessions
- 第十一周PSP
- 我和Java有个约定
- iOS 学习 - 14.本地联系人
- CodeForces#275--DIV 2--A
- POI读取/写入Excel文件
- 发送广播BroadcastReceiver
- 九度OJ1468
- ArcGIS Server10.2服务启动不了之http://localhost:6080/arcgis/manager无法打开之arcMap 无法打开6080admin问题解决之路
- iOS开发——开发必备OC篇&;UITableView设置界面完整封装(四)
- 监控服务器JVM内存运行
- Linux下几个常用的快捷键,真的很实用
- live555学习经验链接二
- VS2012使用XListCtrl
- Web服务器自定义错误页面
- spark ML pipeline 学习
- HEX SDUT 3896 17年山东省赛D题
- MySQL数据备份方法
- bootstrap源码之滚动监听组件scrollspy.js详解
- getting data from the keybroad
热门文章
- F - Truck History
- [Windows Server]安装系统显示“缺少计算机所需的介质驱动程序”解决方案
- [SharePoint2010开发入门经典]9创建更好的用户体验----silverlight
- Android获取图片实际大小兼容平板电脑
- warning:deprecated conversion from string constant to &;#39;char *&;#39;
- MySql 基础学习笔记 1——概述与基本数据类型: 整型: 1)TINYINT 2)SMALLINT 3) MEDIUMINT 4)INT 5)BIGINT 主要是大小的差别 图 浮点型:命令
- Android应用之——自己定义控件ToggleButton
- BZOJ 2435: [Noi2011]道路修建 dfs搜图
- 多年iOS开发经验总结(一)
- 谷歌开源可视化工具Facets,将用于人+AI协作项目研究——无非就是一个用于特征工程探索的绘图工具集,pandas可以做的