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 阅读数:10 评论数: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