游客 注册 | 登录
中文 | En

1919 - 道路规划

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

有N个村庄,编号从1到N,请你建立一些道路,使得任意两个村庄可以相连。我们说两个村A和B是相连的,当且仅当有一条公路在A与B之间,或存在一个村庄C,有一条的道路连接着A和C之间,一条连接着B和C。

我们知道,已经有一些道路在一些村庄之间,你的工作是再建一些道路,使得所有的村庄连接并且所有的道路建造总和最低。

题目输入

第一行是一个整数N(3 <= N <= 100),表示村庄的数量。接下来N行,每行包含N个整数,在这N行中的第i行的第j个整数Aij表示村庄i到村庄j建立道路的费用 (1 <= Aij <= 1000)。

然后有一个整数Q(0 <= Q <= N *(N + 1)/2)。接下来再Q行,每一行包含两个整数a和b(1 <= a < b <= N),即村庄a和b之间已经建成道路。

题目输出

你应该输出一行包含一个整数,表示所有村庄都连接所要建设道路的最小费用。

输入/输出样例

输入格式

3
0 990 692
990 0 179
692 179 0
1
1 2

输出格式

179

C++解答

//求某些点已经被连接的 最小生成树
#include <stack>
#include <set>
#include <vector>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 102
int map[N][N];
bool b[N];
int n;
int Prim()
{
    int i,sum=0,k;
    int t=n;
    int Min;
    memset(b,0,sizeof(b));
    while(--t)
    {
        Min=10000;
        for(i=2;i<=n;i++)
         if(!b[i]&&Min>map[1][i])
          {
              Min=map[1][i];
              k=i;
          }
       //   printf("%d ",Min);
          b[k]=1;
          sum+=Min;
          for(i=2;i<=n;i++)
           if(!b[i]&&map[k][i]<map[1][i])
             map[1][i]=map[k][i];
    }
    return sum;
}
int main()
{
  //  freopen("roads.in", "r", stdin);
  //  freopen("roads.out", "w", stdout);
    int i,j,q;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
         for(j=1;j<=n;j++)
          scanf("%d",&map[i][j]);
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d %d",&i,&j);
            map[i][j]=0;
            map[j][i]=0;
        }
        printf("%d\n",Prim());
    }
    return 0;
}
请先登陆