Poj 1251 Jungle Roads (邻接表 + 优先队列 + Prime 最小生成树)

素颜马尾好姑娘i 2022-08-27 03:54 166阅读 0赞

突然翻出了几份之前写的代码，拿出来回顾一下。

题意：求保持森林中每个村子都有道路相通,且维修所需要的最少money

#include <iostream>
    #include <queue>
    using namespace std;
    
    const int INF = 0x5fffffff;  //权值上限  
    const int MAXPT = 30;       //顶点数上限  
    const int MAXEG = 1000;     //边数上限 
    
    class Prim     /*邻接表 + 优先队列 + Prime 最小生成树*/
    {  
    private:  
        int n,e;  //n个点
        int dis[MAXPT],head[MAXPT];
        bool visit[MAXPT];
      
        struct Node  
        {
            int v,dis;
            Node () {}
            Node (int _v,int _dis)
            {
                v=_v;
                dis=_dis;
            }
            bool operator < (const Node a) const
            {
                return dis>a.dis;
            }
        };
    
        struct Edge
        {
            int v, w, next;
            Edge () {}
            Edge (int _v, int _next, int _w)
            {
                v=_v;
                next=_next;
                w=_w;
            }
        }edges[MAXEG];
    
    public:
    	inline void init (int vx)
        {
            n = vx;
            e = 0;
            memset(head,-1,sizeof(int) * (vx + 1));
    		memset(visit,false,sizeof(visit));
        }
        
        inline void Add (int u, int v, int w)
        {
            edges[e] = Edge(v, head[u], w);
            head[u] = e++;
        }
    
    	int prim (int src)
    	{
    		int cost=0,cnt=0;
    		Node first;
    		priority_queue<Node> Q;
    		Q.push (Node(src, 0));
    		while (!Q.empty() && cnt < n)
    		{
    			first=Q.top();
    			Q.pop ();
    			if (visit[first.v])
    				continue;
    			cost+=first.dis;
    			cnt++;
    			visit[first.v]=true;
    			
    			for (int i=head[first.v];i!=-1;i=edges[i].next)
    				if (!visit[edges[i].v])
    					Q.push (Node (edges[i].v,edges[i].w));
    		}
    		return cost;
    	}
    }ob;
    
    
    int main ()
    {
    	int n;
    	char str[5];
    	while (~scanf("%d",&n),n)
    	{
    		ob.init (n);
    		for (int i=1;i<n;i++)
    		{
    			int q,x,y,temp;
    			scanf("%s%d",str,&q);
    			x=str[0]-64;                               //将A变成1,将B变成2,以此类推
    			while (q--)
    			{
    				scanf("%s%d",str,&temp);
    				y=str[0]-64;
    				ob.Add(x,y,temp);
    				ob.Add(y,x,temp);
    			}
    		}
    		printf("%d\n",ob.prim(1));
    	}
    	return 0;
    }