【luogu P3366 最小生成树】 题解 Prim
include
include
include
include
using namespace std;
const int maxn = 505000;
int n, m, dis[maxn], vis[maxn], ans;
struct edge{
int from, to, next, len;
}e[maxn<<2];
int head[maxn], cnt;
void add(int u, int v, int w)
{
e[++cnt].from = u;
e[cnt].len = w;
e[cnt].next = head[u];
e[cnt].to = v;
head[u] = cnt;
}
void Prim()
{
//for(int i = 1; i <= n; i++) dis[i] = 9999;
memset(dis, 127, sizeof(dis));
dis[1] = 0;
for(int i = 1; i <= n; i++)
{
int k = -1, minn = 0x7fffffff;
for(int j = 1; j <= n; j++)
if(dis[j] < minn && !vis[j])
{
k = j;
minn = dis[j];
}
if(k == -1)
{
ans = -1; break;
}
vis[k] = 1; ans += dis[k];
for(int j = head[k]; j != -1; j = e[j].next)
{
int v = e[j].to;
if(!vis[v] && dis[v] > e[j].len)
dis[v] = e[j].len;
}
}
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d",&n, &m);
for(int i = 1; i <= m; i++)
{
int u, v, w;
scanf("%d%d%d",&u, &v, &w);
add(u, v, w), add(v, u, w);
}
Prim();
if(ans == -1)
{
printf("orz\n");
return 0;
}
else
{
printf("%d\n",ans);
return 0;
}
}
最新文章
- js中Window 对象及其的方法
- STM32之PWM君
- MapReduce Shuffle过程
- python序列
- VBA_Excel_教程：Option，错误处理
- Linux-LNMP LAMP LNMPA
- IntellijIdea中常用的快捷键
- CDN-内容推送网络
- Android学习之电话拨号器
- poj1220：高精度进制转换模板题
- Android短信拦截和电话拦截
- JS算法与数据结构之八皇后(晕晕)
- Spring Cloud 之 服务注册与发现
- 递归----Python
- 大道至简第一章Java伪代码
- ASP.NET应用使用Nginx做负载均衡遇到的一个问题
- sqlalchemy 模型中添加根据身份证号计算性别和年龄
- http://www.rabbitmq.com/documentation.html
- java web 程序---jsp连接mysql数据库的实例基础+表格显示
- 区别script中的type=”text/javascript”和language=”Javascript”