布线问题
时间限制：1000 ms | 内存限制：65535 KB
难度：4
- 描述
- 南阳理工学院要进行用电线路改造，现在校长要求设计师设计出一种布线方式，该布线方式需要满足以下条件：
1、把所有的楼都供上电。
2、所用电线花费最少- 输入
- 第一行是一个整数n表示有n组测试数据。(n<5)
每组测试数据的第一行是两个整数v,e.
v表示学校里楼的总个数(v<=500)
随后的e行里，每行有三个整数a,b,c表示a与b之间如果建铺设线路花费为c(c<=100)。（哪两栋楼间如果没有指明花费，则表示这两栋楼直接连通需要费用太大或者不可能连通）
随后的1行里，有v个整数,其中第i个数表示从第i号楼接线到外界供电设施所需要的费用。( 0<e<v*(v-1)/2 )
（楼的编号从1开始），由于安全问题，只能选择一个楼连接到外界供电设备。
数据保证至少存在一种方案满足要求。 - 输出
- 每组测试数据输出一个正整数,表示铺设满足校长要求的线路的最小花费。
- 样例输入
-
1 4 6 1 2 10 2 3 10 3 1 10 1 4 1 2 4 1 3 4 1 1 3 5 6
- 样例输出
-
4
最小生成树，Prim算法 Kruskal算法
Prim算法，没啥好说的，known数组可以与dist数组合并成一个数组使用。不过已经有邻接矩阵这么大（N^2）的空间浪费了，再节省这么点（N）的空间，也没什么变化。
01.#include
<iostream>02.#include
<cstring>03.using namespace std;04.#define
maxN 50205.#define
inf 1000006. 07.int v,e,con[maxN][maxN],known[maxN],dist[maxN];08. 09.int Prim()10.{11.int i,j,choice,sum=0;12.for(i=1;i<=v;i++)13.{14.dist[i]=con[1][i];//从节点1开始15.known[i]=false;16.}17.known[1]=true;18.for(i=1;i<v;i++)19.{20.int min=inf;21.for(j=1;j<=v;j++)22.{23.if(!known[j]&&dist[j]<min)//寻找未知节点中距离最短的节点24.{25.min=dist[j];26.choice=j;27.}28.}29.sum+=dist[choice];30.known[choice]=true;31.for(j=1;j<=v;j++)//更新未知节点中与该节点相连节点的距离32.{33.if(!known[j]&&con[j][choice]<dist[j])34.dist[j]=con[j][choice];35.}36.}37.return sum;38.}39. 40.int main()41.{42.int n,a,b,c;43.cin>>n;44.while(n--)45.{46.cin>>v>>e;47.for(int i=1;i<=v;i++)48.con[i][i]=0;49.for(int i=1;i<v;i++)50.for(int j=i+1;j<=v;j++)51.con[i][j]=con[j][i]=inf;52.while(e--)53.{54.cin>>a>>b>>c;55.con[a][b]=c;56.con[b][a]=c;57.}58.int min=inf,tmp;59.for(int i=1;i<=v;i++)60.{61.cin>>tmp;62.if(tmp<min)min=tmp;63.}64.min+=Prim();65.cout<<min<<endl;66.}67.return 0;68.}
Kruskal算法
不得不感慨下啊，平时看书，似乎都理解了优先队列啊，各种算法啊，可真到写的时候，就写不出来啦，还是要练练啊。
不练，还真不知道operator<的情况下，竟然是大根堆。也就是第17行，一开始写成小于，怎么就总不对呢，原来小于的时候出大根堆
（不知为何，声明bool operator<(const edge &a)的时候，编译总是报错：左参不为const。我把operator<声明在struct edge里，怎么让左参为const呢？）
01.#include
<iostream>02.#include
<queue>03.using namespace std;04.#define
maxN 50205. 06.struct edge07.{08.int u;09.int v;10.int weight;11.};12. 13.struct compare14.{15.bool operator()(edge
&a,edge &b)16.{17.return a.weight>b.weight;18.}19.};20. 21.int parent[maxN],v,e;22. 23.int find(int x)24.{25.if(parent[x]==x)return x;26.return parent[x]=find(parent[x]);27.}28. 29.int Kruskal(priority_queue<edge,vector<edge>,compare>
&pq)30.{31.int edge_count=0,sum=0,up,vp;32.edge
eg;33.while(edge_count<v-1)34.{35.eg=pq.top();36.pq.pop();37.up=find(eg.u);38.vp=find(eg.v);39.if(up!=vp)40.{41.edge_count++;42.sum+=eg.weight;43.parent[vp]=up;44.}45.}46.return sum;47.}48. 49.int main()50.{51.int n,a,b,c;52.cin>>n;53.while(n--)54.{55.cin>>v>>e;56.for(int i=1;i<=v;i++)parent[i]=i;57.priority_queue<edge,vector<edge>,compare>
pq;58.while(e--)59.{60.edge
tmp;61.cin>>tmp.u>>tmp.v>>tmp.weight;62.pq.push(tmp);63.}64.int min=10000,tmp;65.for(int i=0;i<v;i++)66.{67.cin>>tmp;68.if(tmp<min)min=tmp;69.}70.min+=Kruskal(pq);71.cout<<min<<endl;72.}73.return 0;74.}