类似好123门户网站开发复杂么,网盘视频直接做网站,wordpress修改内容,网架结构最优布线问题
ssl 1612
题目大意#xff1a;
求最小生成树
原题#xff1a;
题目描述
学校有n台计算机#xff0c;为了方便数据传输#xff0c;现要将它们用数据线连接起来。两台计算机被连接是指它们之间有数据线连接。由于计算机所处的位置不同#xff0c;因此不同…最优布线问题
ssl 1612
题目大意
求最小生成树
原题
题目描述
学校有n台计算机为了方便数据传输现要将它们用数据线连接起来。两台计算机被连接是指它们之间有数据线连接。由于计算机所处的位置不同因此不同的两台计算机的连接费用往往是不同的。 当然如果将任意两台计算机都用数据线连接费用将是相当庞大的。为了节省费用我们采用数据的间接传输手段即一台计算机可以间接的通过若干台计算机作为中转来实现与另一台计算机的连接。 现在由你负责连接这些计算机你的任务是使任意两台计算机都连通不管是直接的或间接的。
输入
第一行为整数n2n100表示计算机的数目。此后的n行每行n个整数。第x1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。
输出
一个整数表示最小的连接费用。
输入样例
3
0 1 2
1 0 1
2 1 0输出样例
2样例解释
连接1和22和3费用为2
解题思路
用prim的方法也就和Dijkstra差不多只是赋的值不同它是边的权值最后求个和就行了
代码
邻接表
#includecstdio
#includecstring
#includeiostream
using namespace std;
int n,w,h,sum,ans,p[105],f[105],head[105];
struct rec
{int l,to,next;
}a[10005];
int main()
{scanf(%d,n);for (int i1;in;i)for (int j1;jn;j){scanf(%d,a[w].l);if (!a[w].l){--w;continue;}a[w].toj;//邻接表a[w].nexthead[i];head[i]w;}memset(f,0x7f,sizeof(f));f[1]0;for (int i1;in;i){sumf[0];for (int j1;jn;j)if (!p[j]f[j]sum)//求最大{hj;sumf[j];}p[h]1;anssum;for (int jhead[h];j;ja[j].next)//走向其他点f[a[j].to]min(f[a[j].to],a[j].l);//路线的长度}printf(%d,ans);
}邻接矩阵
#includecstdio
#includecstring
#includeiostream
using namespace std;
int n,w,h,x,sum,ans,p[105],f[105],a[105][105];
int main()
{memset(a,0x7f,sizeof(a));//初值memset(f,0x7f,sizeof(f));scanf(%d,n);for (int i1;in;i)for (int j1;jn;j)scanf(%d,a[i][j]);f[1]0;for (int i1;in;i){sumf[0];for (int j1;jn;j)if (!p[j]f[j]sum)//找最大{hj;sumf[j];}p[h]1;anssum;for (int j1;jn;j)f[j]min(f[j],a[h][j]);//替换}printf(%d,ans);
}
