演算法優化小助手：索引優先隊列

hihocoder.com

#1097 : 最小生成樹一·Prim演算法

時間限制:10000ms

單點時限:1000ms

內存限制:256MB

描述

最近，小Hi很喜歡玩的一款遊戲模擬城市開放出了新Mod，在這個Mod中，玩家可以擁有不止一個城市了！

但是，問題也接踵而來——小Hi現在手上擁有N座城市，且已知這N座城市中任意兩座城市之間建造道路所需要的費用，小Hi希望知道，最少花費多少就可以使得任意兩座城市都可以通過所建造的道路互相到達（假設有A、B、C三座城市，只需要在AB之間和BC之間建造道路，那麼AC之間也是可以通過這兩條道路連通的）。

提示：不知道為什麼Prim演算法和Dijstra演算法很像呢Σ(っ °Д °;)っ 。輸入

每個測試點（輸入文件）有且僅有一組測試數據。

在一組測試數據中：

第1行為1個整數N，表示小Hi擁有的城市數量。

接下來的N行，為一個N*N的矩陣A，描述任意兩座城市之間建造道路所需要的費用，其中第i行第j個數為Aij，表示第i座城市和第j座城市之間建造道路所需要的費用。

對於100%的數據，滿足N<=10^3，對於任意i，滿足Aii=0，對於任意i, j滿足Aij=Aji, 0<Aij<10^4.

輸出

對於每組測試數據，輸出1個整數Ans，表示為了使任意兩座城市都可以通過所建造的道路互相到達至少需要的建造費用。

樣例輸入

5

0 1005 6963 392 1182

1005 0 1599 4213 1451

6963 1599 0 9780 2789

392 4213 9780 0 5236

1182 1451 2789 5236 0

樣例輸出

4178

先嘗試用一般的Prim+鄰接矩陣的方式解決：

#include<iostream>#include<vector>#include <climits>using namespace std;int main(){ int n; cin>>n; vector<vector<int>>m(n,vector<int>(n)); vector<int>lowest(n),vertex(n,0); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>m[i][j]; if(!i){ lowest[j]=m[i][j]; } } } vertex[0]=1; int totalcost=0; for(int i=0;i<n;i++){ int mincost=INT_MAX,index=0; for(int j=0;j<n;j++){ if(!vertex[j]&&lowest[j]&&lowest[j]<mincost){ mincost=lowest[j]; index=j; } } vertex[index]=1; totalcost+=lowest[index]; for(int j=0;j<n;j++){ if(m[index][j]&&!vertex[j]&&(m[index][j]<lowest[j]||!lowest[j])){ lowest[j]=m[index][j]; } } } cout<<totalcost<<endl;}

結果：內存崩了

原因：數據是稀疏圖，數組開得太大，利用率太低。

解決方案：改用鄰接表

#include<iostream>#include<vector>#include <climits>using namespace std;class Graph{//鄰接表類 int n; int e; typedef struct arcnode{ int adjvex; arcnode* nextarc; int info; }arcnode; typedef struct { char data; arcnode* firstarc; }vnode; vnode* v;public: Graph(int num){ n=num;e=0; v=new vnode[n]; for(int i=0;i<n;i++){ v[i].firstarc=NULL; v[i].data=NULL; } } ~Graph(){ for(int i=0;i<n;i++){ arcnode*p=v[i].firstarc; while(p){ arcnode*next=p->nextarc; delete p; p=next; } } } vector<pair<int,int>> adj(int a){ vector<pair<int,int>>res; arcnode*p=v[a].firstarc; while(p){ res.push_back(pair<int,int>(p->adjvex,p->info)); p=p->nextarc; } return res; } void insertEdge(int a,int b,int val){ arcnode* isfind=find(a,b); arcnode* p=v[a].firstarc; if(NULL==isfind){ if(NULL==p){ arcnode*temp=new arcnode; temp->adjvex=b; temp->info=val; temp->nextarc=NULL; v[a].firstarc=temp; }else{ while(p->nextarc){ p=p->nextarc; } arcnode*temp=new arcnode; temp->adjvex=b; temp->info=val; temp->nextarc=NULL; p->nextarc=temp; } } } arcnode *find(int a, int b){ arcnode*p=v[a].firstarc; while(p){ if(b==p->adjvex)return p; p=p->nextarc; } return p; } //for test void print(){ for(int i=0;i<n;i++){ cout<<i<<": "; arcnode*p=v[i].firstarc; while(p){ arcnode*next=p->nextarc; cout<<p->adjvex<< <<p->info<< ; p=next; } cout<<endl; } }};int main(){ int n,m; cin>>n>>m; Graph G(n+1);//G[0]不使用 for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; auto temp=G.find(a,b); if(NULL==temp){ G.insertEdge(a, b, c); G.insertEdge(b, a, c); }else if(c<temp->info){ temp->info=c; G.find(b,a)->info=c; } } //G.print(); vector<int>visited(n+1,0); vector<int>lowest(n+1,-1); visited[1]=1; vector<pair<int,int>>p=G.adj(1); for(auto &i:p) lowest[i.first]=i.second; int totalcost=0; for(int i=1;i<n;i++){//循環n-1次 int mincost=INT_MAX,index=-1; for(int j=1;j<=n;j++){ if(!visited[j]&&lowest[j]!=-1&&lowest[j]<mincost){ mincost=lowest[j]; index=j; } } //if(index<=0)continue; visited[index]=1; totalcost+=lowest[index]; p=G.adj(index); for(auto &j:p) if(!visited[j.first]&&(lowest[j.first]==-1||j.second<lowest[j.first])) lowest[j.first]=j.second; } cout<<totalcost<<endl;}

結果：超時了

原因：演算法複雜度為O(V^2)，儘管圖的邊很少，但點太多還是會超時

解決方案：考慮到是稀疏圖，利用索引優先隊列將Prim演算法的複雜度優化為O(ElgE)

#include<iostream>#include<vector>#include <climits>using namespace std;class indexPQ{private: int *pq;//二叉堆，保存的是元素在key中的位置 int *qp;//二叉堆的逆序，pq[qp[i]]=qp[pq[i]]=i; int *key;//保存元素 int sz;// int capacity;//索引優先隊列public: indexPQ(int n){ pq=new int [n+1];//pq[0]不使用 qp=new int [n+1];//qp[0]不使用 for(int i=1;i<=n;i++)qp[i]=-1;//qp[i]=-1表示索引優先隊列i處為空 key=new int [n+1];//qp[0]不使用 sz=0; capacity=n; } ~indexPQ(){ delete []pq; delete []qp; delete []key; } int operator[](int n){ return key[n]; } bool insert(int k ,int val){//在第k個位置將key插入優先隊列,複雜度O(lgN) if(k>capacity)return false; sz++; pq[sz]=k;//第sz個插入索引優先隊列的元素在位置k qp[k]=sz;//位置k是第sz個插入索引優先隊列的元素 key[k]=val;//在位置k保存元素值 swim(sz);//將第sz個插入索引優先隊列的元素放置到堆中合適的位置 return true; } void pop(){ if(sz>0){ exch(1, sz--);//sz要在sink前減少 sink(1); key[pq[sz+1]]=NULL; qp[pq[sz+1]]=-1; } } bool contain(int k){ return qp[k]!=-1; } int top(){ return key[pq[1]]; } int topIndex(){ return pq[1]; } void change(int k,int val){ if(-1==qp[k])insert(k, val); key[k]=val; swim(qp[k]);//將二叉堆中k對應的元素進行上浮下沉處理 sink(qp[k]); } void del(int k){ int index=qp[k]; exch(index,sz--); swim(index); sink(index); key[k]=NULL; qp[k]=-1; } bool empty(){ return sz==0; } int size(){ return sz; } //for test void print(){ for(int i=1;i<=sz;i++)cout<<i<< <<pq[i]<<": "<<key[pq[i]]<<endl; } bool check(){ for(int i=sz;i>=1;i--){ if(i/2>=1){ if(cmp(key[pq[i]],key[pq[i>>1]])){ cout<<"Problem here: "<<qp[i]<< <<pq[i]<<": "<<key[pq[i]]<< <<pq[i>>1]<<": "<<key[pq[i>>1]]<<endl; return false; } } } return true; }private: bool cmp(int a,int b){ return a<b; } void swim(int n){//演算法複雜度O(lgN) while(n>1&&cmp(key[pq[n]],key[pq[n>>1]])){//如果key[pq[n]]優先順序較高，則上浮 exch(n,n>>1); n>>=1; } } void sink(int n){//演算法複雜度O(lgN) while(2*n<=sz){ int k=2*n; if(k<sz&&cmp(key[pq[k+1]],key[pq[k]]))k++;//在左右孩子中選出優先順序高的一個 if(cmp(key[pq[k]],key[pq[n]])){//如果k比n優先順序高，n下沉 //cout<<"Exchange: "<<key[pq[k]]<< <<key[pq[n]]<<endl; exch(n,k); n=k; }else break; } } void exch(int a,int b){ int i=pq[a],j=pq[b]; swap(pq[a],pq[b]); swap(qp[i],qp[j]); }};void dijkstra(int now,vector<int>&ans,vector<vector<int>>&G){//演算法複雜度O(N^2) vector<int>res(G[now]);//初始化距離 vector<int>mark((int)res.size(),0);//訪問標記 for(int i=1;i<(int)res.size();i++){ int minl=INT_MAX,minindex=now; //找到距離該最近的鄰接點 for(int j=1;j<(int)res.size();j++){ if(res[j]>0&&res[j]<minl&&mark[j]==0){ minl=res[j]; minindex=j; } } mark[minindex]=1;//標記此最近的點為已訪問 for(int j=1;j<(int)res.size();j++){ if(G[minindex][j]>0){//如果存在路徑 //如果j與now號未通 //則與j號點最短距離為G[index][j]+res[minindex] //否則取G[minindex][j]+res[minindex]和res[j]的最小值 res[j]=(res[j]>0?min(res[j],G[minindex][j]+res[minindex]):G[minindex][j]+res[minindex]); } } } ans=res;//將結果傳回ans}void dijkstraAndIndexPQ(int now,vector<int>&res,vector<vector<int>>&G){//演算法複雜度O(N^ res=G[now]; indexPQ q((int)res.size()-1); vector<int>mark((int)res.size(),0);//訪問標記 for(int i=1;i<(int)res.size();i++) if(G[now][i]>0)q.insert(i, G[now][i]); for(int i=1;i<(int)res.size();i++){ while(!q.empty()&&mark[q.topIndex()])q.pop(); int index=q.topIndex();q.pop(); mark[index]=1; for(int j=1;j<(int)G[index].size();j++) if(!mark[j]&&G[index][j]>0){ res[j]=(res[j]>0?min(res[j],G[index][j]+res[index]):G[index][j]+res[index]); q.change(j, res[j]); } }}class Graph{ int n; int e; typedef struct arcnode{ int adjvex; arcnode* nextarc; int info; }arcnode; typedef struct { char data; arcnode* firstarc; }vnode; vnode* v;public: Graph(int num){ n=num;e=0; v=new vnode[n]; for(int i=0;i<n;i++){ v[i].firstarc=NULL; v[i].data=NULL; } } ~Graph(){ for(int i=0;i<n;i++){ arcnode*p=v[i].firstarc; while(p){ arcnode*next=p->nextarc; delete p; p=next; } } } vector<pair<int,int>> adj(int a){ vector<pair<int,int>>res; arcnode*p=v[a].firstarc; while(p){ res.push_back(pair<int,int>(p->adjvex,p->info)); p=p->nextarc; } return res; } void insertEdge(int a,int b,int val){ //cout<<"666"<<endl; arcnode* isfind=find(a,b); arcnode* p=v[a].firstarc; if(NULL==isfind){ //cout<<"999"<<endl; if(NULL==p){ arcnode*temp=new arcnode; temp->adjvex=b; temp->info=val; temp->nextarc=NULL; v[a].firstarc=temp; }else{ while(p->nextarc){ p=p->nextarc; } arcnode*temp=new arcnode; temp->adjvex=b; temp->info=val; temp->nextarc=NULL; p->nextarc=temp; } //e++; } } arcnode *find(int a, int b){ arcnode*p=v[a].firstarc; while(p){ if(b==p->adjvex)return p; p=p->nextarc; } return p; } //for test void print(){ for(int i=0;i<n;i++){ cout<<i<<": "; arcnode*p=v[i].firstarc; while(p){ arcnode*next=p->nextarc; cout<<p->adjvex<< <<p->info<< ; p=next; } cout<<endl; } }};int main(){ int n,m; cin>>n>>m; Graph G(n+1);//G[0]不使用 for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; auto temp=G.find(a,b); if(NULL==temp){ G.insertEdge(a, b, c); G.insertEdge(b, a, c); }else if(c<temp->info){ temp->info=c; G.find(b,a)->info=c; } } //G.print(); vector<int>mark(n+1,0); indexPQ q(n); mark[1]=1; vector<pair<int,int>>p=G.adj(1); for(auto &i:p)q.insert(i.first, i.second); int totalcost=0; for(int i=1;i<n;i++){//循環n-1次 while(!q.empty()&&mark[q.topIndex()])q.pop(); int top=q.top(),index=q.topIndex();q.pop(); //cout<<"top: "<<top<<endl; totalcost+=top; mark[index]=1; p=G.adj(index); for(auto &i:p){ if(!q.contain(i.first)||i.second<q[i.first])q.change(i.first, i.second); } } cout<<totalcost<<endl;}

結果：

大功告成~

PS：

廣告時間啦~

理工狗不想被人文素養拖後腿？不妨關注微信公眾號：

推薦閱讀：