题目107：找出连接网络的最高效的方法

欧拉计划

Minimal network

The following undirected network consists of seven vertices and twelve edges with a total weight of 243.

The same network can be represented by the matrix below.

However, it is possible to optimise the network by removing some edges and still ensure that all points on the network remain connected. The network which achieves the maximum saving is shown below. It has a weight of 93, representing a saving of 243 − 93 = 150 from the original network.

Using network.txt (right click and 'Save Link/Target As...'), a 6K text file containing a network with forty vertices, and given in matrix form, find the maximum saving which can be achieved by removing redundant edges whilst ensuring that the network remains connected.

题目：

如下所示的无向网络包含 7 个顶点和 12 条边，边权重之和为 243。

这个网络还可以用如下的矩阵来表示：

但是，在保证网络上所有点之间连通性的前提下，可以将某些边去除掉，从而实现该网络的优化。能够做到最多节省的网络如下所示。其权重和为 93，与原网络相比共节省了 243 − 93 = 150。

p107_network.txt (5.05 KB, 下载次数: 16)

2016-8-18 23:49 上传

点击文件名下载附件

包含一个拥有四十个顶点的网络，以矩阵形式给出。求在保证连通性的前提下，通过去除边可以做到的最多节省。

jerryxjr1220

import numpy as np

a = np.genfromtxt('p107_network.txt', delimiter=',')
sum_s = np.nansum(a / 2)
list_index = [0]
sum_f = 0
while (len(list_index) < len(a)):
    mini = np.nanmin(a[list_index, :])
    index_min = np.where(a[list_index] == mini)
    a[list_index, index_min[1][0]] = 'nan'
    a[index_min[1][0], list_index] = 'nan'
    list_index.append(index_min[1][0])
    sum_f += mini
print(sum_s - sum_f)

259679

guosl

本题是一个典型的最小生成树。我应用了Kruskal算法。
为了读取数据方便我把数据文件中的”-“改成了100000，而把”，“改成了空格。

/*
答案：259679
*/
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 40;
const int INF = 100000;

struct stEdge
{
  int p1, p2;
  int nLen;
  bool operator<(const stEdge& e) const
  {
    return (nLen < e.nLen);
  }
};

vector<stEdge> v;
int r[N];

int findroot(int nId)
{
  if (r[nId] == nId)
    return nId;
  r[nId] = findroot(r[nId]);
  return r[nId];
}

bool mg(int nId1, int nId2)
{
  int rd1 = findroot(nId1);
  int rd2 = findroot(nId2);
  if (rd1 == rd2)
    return false;
  if (rd1 < rd2)
    r[rd2] = rd1;
  else
    r[rd1] = rd2;
  return true;
}

int main(void)
{
  long long nTotalLen = 0;
  for (int i = 0; i < N; ++i)
    r[i] = i;
  //读入数据
  errno_t err;
  FILE* fp = NULL;
  err = fopen_s(&fp,"p107_network.txt", "r");//打开文件
  if (err != 0)
  {
    printf_s("数据文件未打开\n");
    return 0;
  }
  for (int i = 0; i < N; ++i)
  {
    for (int j = 0; j < N; ++j)
    {
      int x = 0;
      fscanf_s(fp, "%d", &x);
      if (j > i && x != INF)
      {
        stEdge e;
        e.p1 = i;
        e.p2 = j;
        e.nLen = x;
        v.push_back(e);
        nTotalLen += x;
      }
    }
  }
  fclose(fp);
  sort(v.begin(), v.end());
  int nMinSum = 0;
  for (int i = 0; i < (int)v.size(); ++i)
  {
    if (mg(v[i].p1, v[i].p2))
      nMinSum += v[i].nLen;
  }
  printf_s("%d\n", nTotalLen - nMinSum);
  return 0;
}