★Agri-Net 最短網絡
農民約翰被選為他們鎮的鎮長！他其中一個競選承諾就是在鎮上建立起互聯網,并連接到所有的農
場.當然,他需要你的幫助.
約翰已經給他的農場安排了一條高速的網絡線路,他想把這條線路共享給其他農場.為了用最小的
消費,他想鋪設最短的光纖去連接所有的農場.你將得到一份各農場之間連接費用的列表,你必須找
出能連接所有農場并所用光纖最短的方案.每兩個農場間的距離不會超過 100000
PROGRAM NAME: agrinet
INPUT FORMAT
第一行: 農場的個數,N（3<=N<=100）.
第二行..結尾: 后來的行包含了一個 N*N 的矩陣,表示每個農場之間的距離.理論上,他們是 N 行,
每行由 N 個用空格分隔的數組成,實際上,他們限制在 80 個字符,因此,某些行會緊接著另一些行.
當然,對角線將會是 0,因為不會有線路從第 i 個農場到它本身.
SAMPLE INPUT (file agrinet.in)
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
OUTPUT FORMAT
只有一個輸出,其中包含連接到每個農場的光纖的最小長度.
SAMPLE OUTPUT (file agrinet.out)

28

模板題prime算法

/*
ID: jinbo wu
TASK:agrinet
LANG: C++
*/
#include<bits/stdc++.h>
using namespace std;
#define INF 100005;
int lowcost[105];
int a[105][105];
bool vis[105];
int main()
{freopen("agrinet.in","r",stdin);freopen("agrinet.out","w",stdout);int n,k;cin>>n;int sum=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];for(int i=1;i<=n;i++)lowcost[i]=a[1][i];for(int i=1;i<=n;i++){int tmp=INF;for(int j=1;j<=n;j++)if(!vis[j]&&tmp>lowcost[j])tmp=lowcost[k=j];sum+=tmp;vis[k]=1;for(int j=1;j<=n;j++)if(!vis[j]&&lowcost[j]>a[k][j])lowcost[j]=a[k][j];}cout<<sum<<endl;}

總結

以上是生活随笔為你收集整理的usaco ★Agri-Net 最短网络的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。