【A - Jungle Roads】

思路：

最小生成树板题。Kruskal（并查集）：存储所有边，sort，遍历一遍边即可找出所有应采用的边，因此也可以使用优先队列。不需要vis[]，并查集足矣。Prim（优先队列）：类似Dijkstra，以点态存优先队列，相当于全图最短路，有所不同的是，最短路松弛为dis[v] = dis[u] + w；最小生成树松弛为dis[v] = w。利用vis[]。可以用邻接表或邻接矩阵。本代码都没用，直接存边了。

代码：

Kruskal：0ms 684kB

​//0ms684kB#include <iostream>#include <cstdio>#include <queue>#include <cstring>#include <algorithm>using namespace std;const int maxn = 105;int N;int ans;int par[maxn];struct EDGE{int u,v,w;friend bool operator < (EDGE a , EDGE b){return a.w < b.w;}}edge[maxn];int cnt = 0;//from 1 .. cntvoid ADDEDGE(int u,int v,int w){cnt++;edge[cnt].u = u;edge[cnt].v = v;edge[cnt].w = w;return ;}void INIT(){cnt = 0;ans = 0;memset(par , -1 , sizeof(par));return ;}int FIND(int i){return par[i] == -1 ? i : par[i] = FIND(par[i]) ;}void UNION(int l,int r){par[r] = l;return ;}void KRUSKAL(){int k=1;while(k<N){for(int i=1;i<=cnt;i++){int l = edge[i].u;int r = edge[i].v;int parl = FIND(l);int parr = FIND(r);if(parl != parr){UNION(parl,parr);ans += edge[i].w;k++;}}}return ;}int main(){while(cin>>N && N){INIT();for(int i=1;i<N;i++){int k;char op;cin>>op>>k;int u = op-'A';while(k--){int w;cin>>op>>w;ADDEDGE(u , int(op-'A') , w);}}sort(edge+1 , edge+cnt+1);KRUSKAL();cout<<ans<<endl;}return 0;}​

Prim：0ms 676kB

​//0ms676kB#include <iostream>#include <cstdio>#include <queue>#include <cstring>#include <algorithm>#define INF 0x3f3f3f3fusing namespace std;const int maxn = 105;int N;int ans;int dis[maxn];bool vis[maxn];struct EDGE{int u,v,w;friend bool operator < (EDGE a , EDGE b){return a.w < b.w;}}edge[maxn];int cnt;//from 1 .. cntvoid ADDEDGE(int u,int v,int w){cnt++;edge[cnt].u = u;edge[cnt].v = v;edge[cnt].w = w;return ;}struct NODE{int id;int dis;friend bool operator > (NODE a , NODE b){return a.dis > b.dis;}NODE(int id,int dis) : id(id) , dis(dis) {} ;};priority_queue <NODE , vector<NODE> , greater<NODE> > Q;void INIT(){cnt = 0;ans = 0;memset(dis , INF , sizeof(dis));memset(vis , 0 , sizeof(vis));return ;}void PRIM(){dis[0] = 0;Q.push(NODE(0 , 0));while(Q.size()){NODE cur = Q.top() ; Q.pop();int id = cur.id;if(!vis[id]){vis[id] = true;ans += dis[id];for(int i=1;i<=cnt;i++){//小心写代码。 int u = edge[i].u;int v = edge[i].v;int w = edge[i].w;if(u == id && !vis[v] && dis[v] > w){dis[v] = w;Q.push(NODE(v , dis[v])); }if(v == id && !vis[u] && dis[u] > w){dis[u] = w;Q.push(NODE(u , dis[u]));}}}}return ;}int main(){while(cin>>N && N){INIT();for(int i=1;i<N;i++){int k;char op;cin>>op>>k;int u = op-'A';while(k--){int w;cin>>op>>w;ADDEDGE(u , int(op-'A') , w);}}PRIM();cout<<ans<<endl;}return 0;}​

如果觉得《【A - Jungle Roads】》对你有帮助，请点赞、收藏，并留下你的观点哦！