1391：局域网(net)
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
某个局域网内有n(n≤100)台计算机，由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用f(i,j)表示i,j之间连接的畅通程度(f(i,j)≤1000)，f(i,j)值越小表示i,j之间连接越通畅，f(i,j)为0表示i,j之间无网线连接。现在我们需要解决回路问题，我们将除去一些连线，使得网络中没有回路，并且被除去网线的Σf(i,j)最大，请求出这个最大值。
【输入】
第一行两个正整数n,k
接下来的k行每行三个正整数i,j,m表示i,j两台计算机之间有网线联通，通畅程度为m。
【输出】
一个正整数，Σf(i,j)的最大值。
【输入样例】
5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2
【输出样例】
8
1. //示例代码 prim算法 2. #include <cstdio> 3. #include <iostream> 4. #include <stdio.h> 5. #include <cstring> 6. using namespace std; 7. const int N=105; // 定义常量 N 为 105 8. int n,k,a,b,m,sum; // n 为点数，k 为边数，a，b，m 分别表示边的起点、终点和权值 9. int g[N][N]; // 存储图的邻接矩阵 10. int minn[N]; // 存储每个点到已选节点集合的最小边权 11. bool u[N]; // 标记每个节点是否已经加入最小生成树中 12. int main() 13. { 14. scanf("%d %d",&n,&k); // 输入点数和边数 15. memset(g,0x3f,sizeof(g)); // 邻接矩阵初始化为无穷大 16. memset(minn,0x3f,sizeof(minn)); // minn 数组初始化为无穷大 17. memset(u,true,sizeof(u)); // 标记数组初始化为 true 18. 19. for(int i=1;i<=k;i++){ // 输入边信息，并在邻接矩阵中对应位置赋权值 20. scanf("%d %d %d",&a,&b,&m); 21. g[a][b]=g[b][a]=m; 22. sum+=m; // 统计权值和 23. } 24. 25. minn[1]=0; // 对任意一点的最小边权初始化为 0 26. for(int i=1;i<=n;i++){ // 寻找 n-1 条边构成的最小生成树 27. int t=0; // 选出到已选节点集合距离最小的点 28. for(int j=1;j<=n;j++) 29. if(u[j] && minn[j]<minn[t]) t=j; 30. u[t]=false; // 标记 t 为已选节点 31. for(int j=1;j<=n;j++) // 更新 t 到未选节点距离的最小值 32. if(u[j]&&g[t][j]<minn[j]) minn[j]=g[t][j]; 33. } 34. int ans=0; 35. for(int i=1;i<=n;i++) ans+=minn[i]; // 计算最小生成树的权值和 36. ans=sum-ans; // 总权值减去最小生成树权值和得到答案 37. printf("%d",ans); // 输出答案 38. return 0; // 完美结束 39. }
1. // 示例代码 Kruskal算法 2. #include <algorithm> 3. #include <cstdio> 4. #include <cstring> 5. #include <iostream> 6. #include <stdio.h> 7. 8. using namespace std; 9. 10. const int N = 105; 11. int n, k, sum, tj; 12. 13. // 存储边的结构体 14. struct node { 15. int x, y, z; 16. } a[N * N]; 17. 18. // 求并查集中的祖先 19. int f[N]; 20. int find(int x) { 21. if (f[x] == x) 22. return x; 23. return f[x] = find(f[x]); 24. } 25. 26. // 边权排序函数 27. bool cmp(const node &a, const node &b) { return a.z <= b.z; } 28. 29. int main() { 30. // 输入 31. scanf("%d %d", &n, &k); 32. for (int i = 1; i <= k; i++) { 33. scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z); 34. sum += a[i].z; 35. } 36. 37. // 初始化并查集 38. for (int i = 1; i <= n; i++) 39. f[i] = i; 40. 41. // 边权排序 42. sort(a + 1, a + k + 1, cmp); 43. 44. // Kruskal算法主体部分 45. for (int i = 1; i <= k; i++) { 46. int fx = find(a[i].x); 47. int fy = find(a[i].y); 48. if (fx != fy) { 49. f[fy] = fx; 50. sum -= a[i].z; 51. tj++; 52. } 53. if (tj == n - 1) 54. break; 55. } 56. 57. // 输出答案 58. printf("%d", sum); 59. return 0; 60. }
