这个问题需要求解在一个城市网中，连接所有城市的最小代价，一个典型的最小生成树问题。

需要注意的是，每个城市只能朝一个方向修路，所以两个城市之间的最小代价不是（X+Y）/2，而是Max（X,）

解决方案如下：

using System;

using System.Collections.Generic;

using System.Collections;

using System.Text;

//最小生成树问题

public class CityLink

{

int N;

bool[,] map;

bool[] visited;

bool AllConnect()

{

  visited = new bool[N];//very importent!!!!

  dfs(0);

  for (int i = 0; i < N; i++)

    if (!visited[i])

       return false;

  return true;

}

void dfs(int i)

{

  visited[i] = true;

  for (int j = 0; j < N; j++)

    if (map[i, j] && !visited[j])

      dfs(j);

}

public int timeTaken(int[] x, int[] y)

{

  N = x.Length;

  int[,] d = new int[N, N];

  map = new bool[N, N];

  List<int> edgesv = new List<int>();//所有不同长度的边

  Hashtable edges = new Hashtable();//每个边都连接了哪些顶点

  for (int i = 0; i != N; i++)

    for (int j = i; j != N; j++)

    {

      if (x[i] == x[j])

        d[i, j] = (Math.Abs(y[i] - y[j]) + 1) / 2;

      else if (y[i] == y[j])

        d[i, j] = (Math.Abs(x[i] - x[j]) + 1) / 2;

      //只能朝一个方向走，不能改变方向？

      else

        d[i, j] = Math.Max(Math.Abs(x[i] - x[j]), Math.Abs(y[i] - y[j]));

        //d[i, j] = (Math.Abs(x[i] - x[j]) + Math.Abs(y[i] - y[j]) + 1) / 2;

      if (!edgesv.Contains(d[i, j]))

        edgesv.Add(d[i, j]);

      if (edges.Contains(d[i, j]))

      {

        ((List<int>)edges[d[i, j]]).Add(i);

        ((List<int>)edges[d[i, j]]).Add(j);

      }

      else

      {

        List<int> tmp = new List<int>();

        tmp.Add(i);

        tmp.Add(j);

        edges.Add(d[i, j], tmp);

      }

    }

  edgesv.Sort();//Kruskal算法需要从最小的边开始，所以这里排序一下

  //Kruskal

  for (int i = 0; i < edgesv.Count; i++)

  {

  //Conect two points

    List<int> points = (List<int>)edges[edgesv[i]];

    for (int j = 0; j < points.Count; j += 2)

    {

      map[points[j], points[j + 1]] = true;

      map[points[j+1], points[j]] = true;

    }

    if (AllConnect())

      return edgesv[i];

  }

  return -1;

}

>

---

Ecogiser's Blog