Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

POJ 1251 Jungle Roads

SSummerZzz 2019-11-08 19:29:00 阅读数:53 评论数:0 点赞数:0 收藏数:0

题目链接:https://vjudge.net/problem/POJ-1251

思路:题目说路太多,需要去掉一些路,使得维修费用减少,前提需要所有乡村能相互到达,问最少需要

多少费用。最小生成树板子题。(本人习惯于直接打堆优化的)

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;

typedef long long LL;
 #define inf 1e9
#define rep(i,j,k) for(int i = (j); i <= (k); i++)
#define rep__(i,j,k) for(int i = (j); i < (k); i++)
#define per(i,j,k) for(int i = (j); i >= (k); i--)
#define per__(i,j,k) for(int i = (j); i > (k); i--)
const int N = ;
 int head[N];
 int dis[N];
 bool vis[N];
 int cnt;
 int n;

struct Edge{
 int to;
 int w;
 int nxt;
 }e[N*N];

struct node{
 int u;
 int w;

friend bool operator<(const node& a,const node& b){
 return a.w > b.w;
  }
 };

priority_queue<node> que;

void add(int u,int v,int w){
 e[cnt].to = v;
 e[cnt].w = w;
 e[cnt].nxt = head[u];
 head[u] = cnt++;
 }

int prime(){

while(!que.empty()) que.pop();

rep(i,,n){
 vis[i] = false;
 dis[i] = inf;
  }
 dis[] = ;
 que.push(node{,dis[]});

int u,v,w;
 while(!que.empty()){
 u = que.top().u;
  que.pop();
 if(vis[u]) continue;
 vis[u] = true;
 for(int o = head[u]; ~o; o = e[o].nxt){
 v = e[o].to;
 w = e[o].w;

if(!vis[v] && dis[v] > w){
 dis[v] = w;
  que.push(node{v,dis[v]});
  }
  }
  }

int ans = ;
 rep(i,,n) ans += dis[i];
 return ans;
 }

int main(){

ios::sync_with_stdio(false);
 cin.tie();

char U,V;
 int u,v;
 int num,w;
 while(cin >> n && n){

rep(i,,n) head[i] = -;
 cnt = ;

rep(i,,n-){
 //开始点 数目
cin >> U >> num;
 u = U - 'A' + ;
 rep(j,,num){
 cin >> V >> w;
 v = V - 'A' + ;
  add(u,v,w);
  add(v,u,w);
  }
  }

cout << prime() << endl;
  }

return ;
 }

 

版权声明
本文为[SSummerZzz]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/SSummerZzz/p/11822846.html