村村通(最小生成树)

2627 村村通

 

 时限: 1
s

 空间范围: 3三千KB

 标题等级 : 黄金
高尔德

题解

 查看运营结果

 

 

题材叙述 Description

村民John被选为他们镇的区长!他个中3个公投承诺就是在镇上建立起网络,并接连到拥有的农场。当然,他供给你的帮带。

John已经给他的农场配置了一条飞快的网络线路,他想把那条路线共享给其余农场。为了用非常的小的消费,他想铺设最短的光导纤维去老是全部的农场。

你将获得一份各农场里边总是开销的列表,你必须找出能再而三全数农场并所用光导纤维最短的方案。每四个农场间的离开不会超越100000

输入描述 Input Description

第2行: 农场的个数,N(3<=N<=100)。
第2行,有些行会紧接着另一对行。当然,对角线将会是0,因为不会有路经从第i个农..结尾:
后来的行李包裹涵了四个N*N的矩阵,表示每一个农场里面的离开。理论上,他们是N行,每行由N个用空格分隔的数组成,实际上,他们限制在77个字符,由此场到它自个儿。

输出描述 Output Description

唯有八个输出,在那之中带有连接到各个农场的光导纤维的细小长度。

样例输入 Sample Input

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

样例输出 Sample Output

28

数据范围及提醒 Data Size & Hint

暂且无界定。

codevs——1243 互连网提速

 时间限制: 1
s

 空间限制: 128000KB

 标题等级 : 黄金
高尔德

题解

  

标题叙述 Description

某高校的高校网由n(1<=n<=50)台微型总结机组成,总括机之间由网线相连,如图5。个中顶点代表总结机,边表示网线。正如你所见,分裂网线的传导能力不完全一样,例如总计机1与电脑2之内传输音讯须要34秒,而总括机2与电脑3中间的传输音信一旦10秒。总括机1与计算机5之间传输音讯需求44秒,途径为机1到机3到机5。

现高校购销了m(1<=m<=10)台加速装备,每台装备可效果于一条网线,使网线上传输信息用时减半。多台装备可用于同一条网线,其意义叠加,即用两台设备,用时为原本的肆分之一,用三台装备,用时为原本的八分之一。怎么着合理利用那个设备,使总括机1到电脑n传输用时最少,那几个标题急需化解。校方请你编制程序消除那几个难点。例如图5,若m=2,则将两台装备分别用于1-3,3-5的路线,传输用时可削减为22秒,那是最棒解。

输入描述 Input Description

第2行先输入n,m。以下n行,每行有n个实数。第i行第j列的数为总结机i与总计机j之间网线的传导用时,0意味它们之间没有网线连接。注意输入数据中,从总计机1到计算机n至少有一条网路。

 

出口描述 Output Description

出口计算机1与总括机n之间传输消息的最短时间。(保留两位小数)

样例输入 萨姆ple Input

5 2

0 34 24 0 0

34 0 10 12 0

24 10 0 16 20

0 12 16 0 30

0 0 20 30 0

样例输出 Sample Output

22.00

 

思路:先对总体举行处理,然后跑一回最短路(笔者用的是spfa),在这些spfa中丰裕dp来消除那道题。

首先:大家在这里存边的时候我们接纳的是1个三维数组,用a[i][j][0]存大家输入的每条边的边权。

       
从a[i][j][1]到a[i][j][k]存的是咱们只要在那条边上使用k个加快器后发生的职能。(当然,里面边不随处的权值赋成一点都不小值,那样就有利于大家前边用来跑spfa)

然后那样大家就把1个比较复杂的难点转化成了2个相比简单的题材了。

对于那个难题大家就足以看做3个差不多的spfa了。

而是别安心乐意的太早,我们并不是就以此样子就能够A掉那个题的啊,大家还要再加一点东西。

专注:spfa里面跑的是三重循环,第①重循环跑源点,第壹重循环跑的是采纳的加快器的个数。

代码:

#include<stdio.h>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100
#define M 20
#define oo 1234567
using namespace std;
int n,m,q[N*N];
double dis[N][M],a[N][N][M];
bool b[N]={0};
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void spfa()
{
    int head(0),tail(1),u;
    q[1]=1;
    b[1]=1;
    do
      {
           head++;
           u=q[head];
           b[u]=0;
           for (int i=1;i<=n;i++)
             if (i!=u)
               for (int j=0;j<=m;j++)//从1到u使用j个加速器 
                 for (int k=0;k<=m-j;k++)//从u到i使用k个加速器,同时要保证j+k<=m 
                   if (dis[u][j]+a[u][i][k]<dis[i][j+k])
                     {
                          dis[i][j+k]=dis[u][j]+a[u][i][k];
                          if (!b[i]) q[++tail]=i,b[i]=1;
                   }
      }while (head<tail);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      {
          scanf("%lf",&a[i][j][0]);
          if(!a[i][j][0])
           for(int k=0;k<=m;k++)
          a[i][j][k]=oo;
        else 
         for(int k=1;k<=m;k++)
          a[i][j][k]=a[i][j][k-1]/2;
      }
    for(int i=2;i<=n;i++)
     for(int j=0;j<=m;j++)
       dis[i][j]=oo;
    spfa();
    printf("%.2lf",dis[n][m]);
    return 0;
}

分拣标签 Tags 点此展开 

 

最小生成树 图论

 

代码:

#include<stdio.h>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100001
#define maxn 1234567
using namespace std;
int n,a[101][101],sum,tot,fa[N],ans;
struct Edge 
{
    int x,y,z;
}edge[N];
int cmp(Edge a,Edge b)
{
    return a.z<b.z;
}
int found(int x)
{
    return fa[x]==x?x:fa[x]=found(fa[x]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      {
          scanf("%d",&a[i][j]);
          edge[++tot].x=i;
          edge[tot].y=j;
          edge[tot].z=a[i][j];
      }
    sort(edge+1,edge+1+tot,cmp);
    for(int i=1;i<=n;i++)
     fa[i]=i;
    for(int i=1;i<=tot;i++)
    {
        int x=edge[i].x,y=edge[i].y;
        int fx=found(x),fy=found(y);
        if(fx!=fy)
        {
            sum++;
            ans+=edge[i].z;
            fa[fy]=fx;
        }
        if(sum==n-1) break;
    }
    printf("%d",ans);
    return 0;
}