题意:无向图,给n个点,n^2条边,每条边有个一权值,其中有k个点有发电站,给出这k个点的编号,选择最小权值的边,求使得剩下的点都能接收到电。
思路:将所有待选边加入优先队列(priority_queue 优先队列),用并查集判断待选边是否符合要求,符合(即不在同一并查集中)则合并。
代码:
/***********************************************/ ll n,k; int a[109]; bool can[109];//此城市是否连通 ll c[109][109]; int st[109]; struct node{ int u,v; int w;//边的权 }; bool operator < (const node& a,const node& b) {//反过来,这样正好优先队列递增 return a.w>b.w; } int find(int a) { while(a!=st[a]) a=st[a]; return a; } void add(int a,int b) { int fa=find(a); int fb=find(b); if(fa<fb) st[fb]=fa; else st[fa]=fb; } void Kruskal() { ll ans=0; priority_queue<node>Q; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j && find(i)!=find(j)) { node t; t.u=i; t.v=j; t.w=c[i][j]; Q.push(t); } while(!Q.empty()) { node x=Q.top(); Q.pop(); if(find(x.u)!=find(x.v)) { ans+=c[x.u][x.v]; add(x.u,x.v); } } cout<<ans<<endl; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); cin>>n>>k; for(int i=1;i<=n;i++) st[i]=i; for(int i=1;i<=k;i++){ cin>>a[i]; can[a[i]]=1; if(i>1){ add(a[i],a[i-1]); } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) cin>>c[i][j]; } Kruskal(); return 0; }