APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

C/C++:Prim+堆优化最小生成树模板

2018年9月27日 1765点热度 0人点赞 0条评论

洛谷:P3366 ,和Dijkstra堆优化模板差不多

题目描述

如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出orz

输入输出格式

输入格式:

第一行包含两个整数N、M,表示该图共有N个结点和M条无向边。(N<=5000,M<=200000)

接下来M行每行包含三个整数Xi、Yi、Zi,表示有一条长度为Zi的无向边连接结点Xi、Yi

输出格式:

输出包含一个数,即最小生成树的各边的长度之和;如果该图不连通则输出orz

输入输出样例

输入样例#1:

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出样例#1:
7

Prim+堆优化模板

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;

static const int MAXN = 5005;
static const int MAXM = 200005;

struct node {
	int next,to,dis;
};

node e[MAXM << 1];

int head[MAXN],vis[MAXN],dis[MAXN];
int n,m,cnt,num,sum;

inline void add(int from,int to,int dis) {
	e[++cnt].next = head[from];
	e[cnt].to = to;
	e[cnt].dis = dis;
	head[from] = cnt;
}

void Prim_Heap(int s) {
	memset(dis,0x3f,sizeof dis);
	memset(vis,false,sizeof vis);
	priority_queue <pair <int ,int >, vector < pair <int ,int > >, greater < pair <int ,int > > > Q;
	dis[s] = 0;
	Q.push(make_pair(0,s));
	while(!Q.empty()) {
		int u = Q.top().second;
		int d = Q.top().first;
		Q.pop();
		if(vis[u]) continue;
		num++;
		sum += d; 
		vis[u] = true;
		for(int i = head[u];i;i = e[i].next) {
			int v = e[i].to;
			if(dis[v] > e[i].dis) {
				dis[v] = e[i].dis;
				Q.push(make_pair(dis[v],v));
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for(int i = 1;i <= m;++i) {
		int from,to,dis;
		cin >> from >> to >> dis;
		add(from,to,dis);
		add(to,from,dis);
	}
	Prim_Heap(1);
	if(num == n) printf("%d\n",sum);
	else puts("orz");
	return 0;
}

 

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: C++ Dijkstra OI Prim 图论 最小生成树 树 模板 洛谷
最后更新:2018年12月15日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
我没有经验,还真是抱歉呢 #NOIP提高组#模板整理 中行天依小柠檬借记卡已收到 使用Enlighter替换Crayon Syntax Highlighter插件 waifu2x:开源的图片放大工具 家中组无线网络全覆盖
标签聚合
HTML 日常 洛谷 C++ OI 动漫 C/C++ ST
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang