「CODEVS1231」最优布线问题

2013年11月22日4,7360

题目描述

学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们中间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。

当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。

现在由你负责连接这些计算机，你的任务是使任意两台计算机都连通（不管是直接的或间接的）。

输入

第1行为整数n（2<=n<=100），表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。

输出

输出只有一个整数，表示最小的连接费用。

示例输入

0 1 2

1 0 1

2 1 0

示例输出

2

提示

知识扩展：本算法在移动通信、智能交通、移动物流、生产调度等物联网相关领域都有十分现实的意义，采用好的算法，就能节省成本提高效率。

代码

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	int n,f[101][101];
	int mn[101];
	bool u[101];
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		    cin>>f[i][j];
	memset(mn,127,sizeof(mn));	    
    memset(u,1,sizeof(u));//蓝点1，白点0
    mn[1]=0;
    for(int i=1;i<=n;i++)
    {
    	int k=0;
    	for(int j=1;j<=n;j++)
 	       if(u[j]&&mn[j]<mn[k])
 	          k=j;
        u[k]=0;
        for(int j=1;j<=n;j++)
            if(u[j]&&f[k][j]<mn[j])
               mn[j]=f[k][j];
    }
    int ans=0;
    for(int i=1;i<=n;i++)
       ans+=mn[i];
    cout<<ans;
    return 0;
}

#include<iostream>

#include<cstring>

using namespace std;

int main()

{

int n,f[101][101];

int mn[101];

bool u[101];

cin>>n;

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

cin>>f[i][j];

memset(mn,127,sizeof(mn));

memset(u,1,sizeof(u));//蓝点1，白点0

mn[1]=0;

for(int i=1;i<=n;i++)

{

int k=0;

for(int j=1;j<=n;j++)

if(u[j]&&mn[j]<mn[k])

k=j;

u[k]=0;

for(int j=1;j<=n;j++)

if(u[j]&&f[k][j]<mn[j])

mn[j]=f[k][j];

}

int ans=0;

for(int i=1;i<=n;i++)

ans+=mn[i];

cout<<ans;

return 0;

}

「CODEVS1078」最短网络(最小生成树) »

hzwer.com _ Home | http://hzwer.com

「CODEVS1231」最优布线问题

题目描述

输入

输出

示例输入

示例输出

提示

代码

分类目录

热门文章

Myfriends

近期评论