最短网络Agri-Net
生活随笔
收集整理的這篇文章主要介紹了
最短网络Agri-Net
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
【例4-11】、最短網絡Agri-Net 【問題描述】 農民約翰被選為他們鎮的鎮長！他其中一個競選承諾就是在鎮上建立起互聯網，并連接到所有的農場。當然，他需要你的幫助。約翰已經給他的農場安排了一條高速的網絡線路，他想把這條線路共享給其他農場。為了用最小的消費，他想鋪設最短的光纖去連接所有的農場。你將得到一份各農場之間連接費用的列表，你必須找出能連接所有農場并所用光纖最短的方案。每兩個農場間的距離不會超過100000。 【輸出格式】 只有一個輸出，其中包含連接到每個農場的光纖的最小長度。 【輸入樣例】agrinet.in 4 0? 4? 9? 21 4? 0? 8? 17 9? 8? 0? 16 21 17 16? 0 【輸出樣例】agrinet.out 28 1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5 struct k{
6 int x,y,v;
7
8 }a[10000];
9 int fa[1000];
10 int find(int x)
11 {
12 if(fa[x]!=x)
13 {fa[x]=find(fa[x]);
14 return fa[x];
15 }
16 else
17 return x;
18 }
19 void un(int x,int y)
20 {
21 fa[x]=y;
22 }
23 int cmp( k a, k b)
24 {
25 if (a.v < b.v) return 1;
26 else return 0;
27 }
28 int main()
29 {
30 int s,m=0;
31 int n;
32 cin>>n;
33 for(int i=1;i<=n;i++)
34 {
35 for(int j=1;j<=n;j++)
36 {
37 cin>>s;
38 if(s!=0)
39 {
40 m++;
41 a[m].x=i;
42 a[m].y=j;
43 a[m].v=s;
44 }
45 }
46 }
47 for(int i=1;i<=n;i++)
48 {
49 fa[i]=i;
50 }
51 sort(a+1,a+m+1,cmp);
52 int k=0,tot=0;
53 for(int i=1;i<=m;i++)
54 {
55 int r=find(a[i].x);
56 int rr=find(a[i].y);
57 if(r!=rr)
58 {
59 un(r,rr);
60 tot+=a[i].v;
61 k++;
62 }
63 if(k==n-1)
64 {
65 break;
66 }
67 }
68 cout<<tot;
69 return 0;
70 }
?
【輸入格式】| 第一行： | 農場的個數，N（3<=N<=100）。 |
| 第二行..結尾 | 后來的行包含了一個N*N的矩陣,表示每個農場之間的距離。理論上，他們是N行，每行由N個用空格分隔的數組成，實際上，他們限制在80個字符，因此，某些行會緊接著另一些行。當然，對角線將會是0，因為不會有線路從第i個農場到它本身。 |
轉載于:https://www.cnblogs.com/lyqlyq/p/6706111.html
總結
以上是生活随笔為你收集整理的最短网络Agri-Net的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： VMware vSphere克隆虚拟机
- 下一篇： 硬盘接口协议