首页 > 代码库 > 最小生成树 prime poj1258
最小生成树 prime poj1258
题意:给你一个矩阵M[i][j]表示i到j的距离 求最小生成树
思路:裸最小生成树 prime就可以了
最小生成树专题
AC代码:
#include "iostream" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #define ll long long #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define mem(a) memset(a,0,sizeof(a)) using namespace std; const int N=50000; struct Edge{ int fr,to; int w; friend bool operator< (Edge a, Edge b){ return a.w>b.w; } }; vector<Edge>Map[N]; void Prime(int n){ int ans=0; Edge now; bool vis[N]; mem(vis); priority_queue<Edge> Q; while(!Q.empty()) Q.pop(); for(int i=0; i<Map[1].size(); ++i) Q.push(Map[1][i]); vis[1]=1; n--; while(n--){ now=Q.top(); Q.pop(); if(vis[now.to])while(vis[now.to]){ now=Q.top(); Q.pop(); } ans+=now.w; vis[now.to]=1; for(int i=0; i<Map[now.to].size(); ++i) if(!vis[Map[now.to][i].to]) Q.push(Map[now.to][i]); } printf("%d\n",ans); } void Add(int u,int v,int w){ Edge e; e.fr=u,e.to=v,e.w=w; Map[u].push_back(e); } int main(){ int t,n,u,v,w; while(~scanf("%d",&n)){ mem(Map),mem(p); for(u=1; u<=n; ++u){ for(v=1; v<=n; ++v){ scanf("%d",&w); if(u!=v) Add(u,v,w),Add(v,u,w); } } Prime(n); } return 0; }
最小生成树 prime poj1258
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。