P1546 最短网络 Agri-Net【MST】
标签：html class 就是 sort 之间 button set play img
题目背景
Farmer John 被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。
题目描述
FJ 已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。
你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过 10^5105。
输入格式
第一行农场的个数 NN（3 \leq N \leq 1003≤N≤100）。
接下来是一个 N \times NN×N 的矩阵，表示每个农场之间的距离。理论上，他们是 NN 行，每行由 NN 个用空格分隔的数组成，实际上，由于每行 8080 个字符的限制，因此，某些行会紧接着另一些行。当然，对角线将会是 00，因为不会有线路从第 ii 个农场到它本身。
输出格式
只有一个输出，其中包含连接到每个农场的光纤的最小长度。
输入输出样例
输入 #1
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
说明/提示
题目翻译来自NOCOW。
USACO Training Section 3.1
思路
黄题难度， 建图跑一遍KRUSKAL就可以了，注意一下路压和边组要开N * N的
CODE
1 #include 2 #include 3 #include 4 #include
5
6 using namespace std;
7 const int maxn = 1e3+7;
8
9 ///把所有边排序，记第i小的边为:e[i](1 10 ///初始化MST为空
11 ///初始化连通分量，让每个点自成一个独立的连通分量
12 ///for(int i = 0; i 13 /// if(e[i].u 和 e[i].v 不在同一个连通分量) {
14 /// 把边e[i]加入MST
15 /// 合并e[i].u 和 e[i].v 所在的连通分量
16 /// }
17 ///}
18
19 int fa[5050],n,m,ans,eu,ev,cnt;
20
21 struct node{
22 int u, v, w;
23 }e[1000007];
24
25 int a[maxn][maxn];
26
27 bool cmp(node a, node b)
28 {
29 return a.w b.w;
30 }
31
32 int fid(int x)
33 {
34 return x == fa[x] ? x : fa[x] = fid(fa[x]);
35 }
36
37 void init(int n)
38 {
39 for(int i = 1; i ) {
40 fa[i] = i;
41 }
42 ans = 0;
43 cnt = 0;
44 }
45
46 bool unite(int r1, int r2)///冰茶鸡
47 {
48 int fidroot1 = fid(r1), fidroot2 = fid(r2);
49 if(fidroot1 != fidroot2) {
50 fa[fidroot2] = fidroot1;
51 return true;
52 }
53 return false;
54 }
55
56 void kruskal(int m)
57 {
58 sort(e+1, e+m+1, cmp);
59 for(int i = 1; i ) {
60 eu = fid(e[i].u);
61 ev = fid(e[i].v);
62 if(eu == ev) {
63 continue;
64 }
65 ans += e[i].w;
66 fa[ev] = eu;
67 if(++cnt == n-1) {
68 break;
69 }
70 }
71 }
72
73 int main()
74 {
75 scanf("%d",&n);
76 init(n);
77 for ( int i = 1; i i ) {
78 for ( int j = 1; j j ) {
79 scanf("%d",&a[i][j]);
80 }
81 }
82 m = 0;
83 for ( int i = 1; i i ) {
84 for ( int j = 1; j j ) {
85 if(i == j)
86 continue;
87 else {
88 e[++m].u = i, e[m].v = j;
89 e[m].w = a[i][j];
90 }
91 }
92 }
93 ans = 0;
94 kruskal(m);
95 cout endl;
96 return 0;
97 }
View Code
P1546 最短网络 Agri-Net【MST】
标签：html class 就是 sort 之间 button set play img
原文地址：https://www.cnblogs.com/orangeko/p/12388839.html
评论