//prim实现
#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std
struct Node
{
int to
int cost
}
int w[102][102]
Node heap[102]
int N,M,res,size
void down(int p)
{
Node n=heap[p]
for(int q=p<<1q<=sizeq<<=1)
{
if(q<size&&heap[q+1].cost!=-1&&heap[q].cost>heap[q+1].cost)
q++
if(heap[q].cost==-1||n.cost!=-1&&n.cost<=heap[q].cost)
{
break
}
heap[p]=heap[q]
p=q
}
heap[p]=n
}
void up(int p)
{
if(heap[p].cost==-1)
return
Node n=heap[p]
for(int q=p>>1q>=1q>>=1)
{
if(heap[q].cost!=-1&&heap[q].cost<=n.cost)
break
heap[p]=heap[q]
p=q
}
heap[p]=n
}
void build()
{
for(int i=size>>1i>0i--)
down(i)
}
void prim()
{
for(int i=2i<=Mi++)
{
heap[i-1].cost=w[1][i]
heap[i-1].to=i
}
size=M-1
build()
res=0
for(int i=1i<Mi++)
{
if(heap[1].cost==-1)
{
res=-1
return
}
res+=heap[1].cost
int v=heap[1].to
heap[1]=heap[size--]
down(1)
for(int j=1j<=sizej++)
{
if(w[v][heap[j].to]!=-1)
{
if(w[v][heap[j].to]<heap[j].cost||heap[j].cost==-1)
{
heap[j].cost=w[v][heap[j].to]
up(j)
}
}
}
}
}
int main()
{
while(scanf("%d%d",&N,&M)!=EOF&&N)
{
memset(w,255,sizeof(w))
int a,b,cost
memset(w,255,sizeof(w))
for(int i=1i<=Ni++)
{
scanf("%d%d%d",&a,&b,&cost)
w[a][b]=w[b][a]=cost
}
prim()
if(res==-1)
printf("?\n")
else
printf("%d\n",res)
}
}
//kruscal实现
#include<iostream>
#include<algorithm>
usingnamespacestd
struct Edge
{
intu,v,w
}
Edge edges[5000]
int parent[102]
intN,M,res
int find(int v)
{
if(parent[v]>0)
parent[v]=find(parent[v])
return parent[v]>0?parent[v]:v
}
voidunion_set(inta,int b)
{
if(parent[a]<=parent[b])
{
parent[a]+=parent[b]
parent[b]=a
}
else
{
parent[b]+=parent[a]
parent[a]=b
}
}
intcmp(Edge e1,Edge e2)
{
return e1.w<e2.w
}
Void kruscal()
{
res=0
memset(parent,255,sizeof(parent))
sort(edges,edges+N,cmp)
intloc=0
int a,b,p1,p2,count=0
bool flag=true
while(loc<N)
{
do
{
loc++
if(loc>N)
{
flag=false
break
}
a=edges[loc].u
b=edges[loc].v
p1=find(a)
p2=find(b)
}while(p1==p2)
if(!flag)
break
res+=edges[loc].w
union_set(p1,p2)
count++
}
if(count<M-1)
res=-1
}
int main()
{
while(scanf("%d%d",&N,&M)!=EOF&&N)
{
for(inti=1i<=Ni++)
scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].w)
kruscal()
if(res==-1)
printf("?\n")
else
printf("%d\n",res)
}
}
步骤如下：
1，需求调研
2，需求分析
3，概要设计
4，详细设计
设计方案内容包括：网络拓扑、IP地址规划、网络设备选型等等。
扩展资料：
网络工程设计原则
网络信息工程建设目标关系到现在和今后的几年内用户方网络信息化水平和网上应用系统的成败。在工程设计前对主要设计原则进行选择和平衡，并排定其在方案设计中的优先级，对网络工程设计和实施将具有指导意义。
1，实用、好用与够用性原则
计算机与外设、服务器和网络通信等设备在技术性能逐步提升的同时，其价格却在逐年或逐季下降，不可能也没必要实现所谓“一步到位”。所以，网络方案设计中应采用成熟可靠的技术和设备，充分体现“够用”、“好用”、“实用”建网原则，切不可用“今天”的钱，买“明、后天”才可用得上的设备。
2，开放性原则
网络系统应采用开放的标准和技术，资源系统建设要采用国家标准，有些还要遵循国际标准(如：财务管理系统、电子商务系统)。其目的包括两个方面：第一，有利于网络工程系统的后期扩充；第二，有利于与外部网络互连互通，切不可“闭门造车”形成信息化孤岛。
3，可靠性原则
无论是企业还是事业，也无论网络规模大小，网络系统的可靠性是一个工程的生命线。比如，一个网络系统中的关键设备和应用系统，偶尔出现的死锁，对于政府、教育、企业、税务、证券、金融、铁路、民航等行业产生的将是灾难性的事故。因此，应确保网络系统很高的平均无故障时间和尽可能低的平均无故障率。
4， 安全性原则
网络的安全主要是指网络系统防病毒、防黑客等破坏系统、数据可用性、一致性、高效性、可信赖性及可靠性等安全问题。为了网络系统安全，在方案设计时，应考虑用户方在网络安全方面可投入的资金，建议用户方选用网络防火墙、网络防杀毒系统等网络安全设施；网络信息中心对外的服务器要与对内的服务器隔离。
5， 先进性原则
网络系统应采用国际先进、主流、成熟的技术。比如，局域网可采用千兆以太网和全交换以太网技术。视网络规模的大小(比如网络中连接机器的台数在250台以上时)，选用多层交换技术，支持多层干道传输、生成树等协议。
6，易用性原则
网络系统的硬件设备和软件程序应易于安装、管理和维护。各种主要网络设备，比如核心交换机、汇聚交换机、接入交换机、服务器、大功率长延时UPS等设备均要支持流行的网管系统，以方便用户管理、配置网络系统。
7，可扩展性原则
网络总体设计不仅要考虑到近期目标，也要为网络的进一步发展留有扩展的余地，因此要选用主流产品和技术。若有可能，最好选用同一品牌的产品，或兼容性好的产品。在一个系统中切不可选用技术和性能不兼容的产品。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）