Agri-Net Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 36780 Accepted: 14825
Description
Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.Input
The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.Output
For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.Sample Input
4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0
Sample Output
28
單純的求最小生成樹普林斯算法,要說是水題,卻不是菜鳥都能輕松過的。且學且刷~~
#include#include using namespace std; int a[101][101],d[101],used[101],n; int main(){ while(cin>>n&&n>=3&&n<=100){ memset(d,0,sizeof(d)); memset(a,0,sizeof(a)); memset(used,0,sizeof(used)); int sum=0; used[0]=1; d[0]=999999; //盡可能大,不要錯寫成0 for(int i=0;i >a[i][j]; for(int k=1;k