洛谷: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; }
文章评论