题目背景
农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。
题目描述
约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。
你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000
输入输出格式
输入格式：
第一行： 农场的个数，N（3<=N<=100）。
第二行..结尾: 后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们限制在80个字符，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有线路从第i个农场到它本身。
输出格式：
只有一个输出，其中包含连接到每个农场的光纤的最小长度。
输入输出样例
输入样例#1：
4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0
输出样例#1：
28
说明
题目翻译来自NOCOW。
USACO Training Section 3.1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | //Prim算法 #include<iostream> #include<cstring> #include<cstdlib> #define Rep1(i,n) for(int i=1;i<=n;i++) using namespace std; int map[101][101]; int lowcost[101]; int n; int prim(){//从编号为1开始 int sum=0; lowcost[1]=0; for(int i=2;i<=n;i++)lowcost[i]=map[1][i]; for(int i=2;i<=n;i++){ int min=0x7fffffff; int minid=0; for(int j=2;j<=n;j++){ if(lowcost[j]<min&&lowcost[j]!=0){ min=lowcost[j]; minid=j; } } sum+=min; lowcost[minid]=0; for(int j=2;j<=n;j++){ if(lowcost[j]>map[minid][j]){ lowcost[j]=map[minid][j]; } } } return sum; } int main(){ ios::sync_with_stdio(false); cin>>n; Rep1(i,n)Rep1(j,n){ cin>>map[i][j]; if(map[i][j]==0)map[i][j]=0x7fffffff; } cout<<prim(); } |
最小生成树算法：
参考：
Prim: http://blog.csdn.net/yeruby/article/details/38615045
Kruskal: http://blog.csdn.net/lulipeng_cpp/article/details/7800865
20180809更新：
Kruskal:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include<iostream> #include<cmath> #include<algorithm> #include<queue> #define ll long long #define pii pair<int,int> #define PINF 0x7fffffff #define NINF 0x80000000 using namespace std; int n; struct edge { int u, v, w; bool operator < (const edge& e2) const { return w < e2.w; } }edges[5000]; int father[105]; int _find(int x) { if (father[x] == 0)return x; return father[x] = _find(father[x]); } bool _union(int x, int y) { x = _find(x); y = _find(y); if (x == y)return false; father[x] = y; return true; } int main() { ios::sync_with_stdio(false); cin >> n; int ePtr = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { int tmp; if (i > j) { ePtr++; edges[ePtr].u = i; edges[ePtr].v = j; cin >> edges[ePtr].w; } else cin >> tmp; } } sort(edges + 1, edges + ePtr + 1); int cnter = 0, len = 0; for (int i = 1; i <= ePtr; i++) { if (_union(edges[i].u, edges[i].v)) { cnter++; len += edges[i].w; } if (cnter == n - 1)break; } cout << len; } |