这道题是最小生成树，但怎么转化是关键。首先是把所有的路都destroy掉，得到基本的MassiveCost，然后在选MST的过程中，遇上这些边相当于还回去，它们的cost就是-destroy[i][j]。这样转化完毕。

用Kruskal来做，注意生成Edge的过程，第二层循环j要从i+1开始，主要是避免把i到i的路也放进去。

此题算是比较经典的K算法的题了。（没有用并查集）

import java.util.*;public class KingdomReorganization{    public int getCost(String[] kingdom, String[] build, String[] destroy)    {        ArrayList
     
       edges = new ArrayList
      
       ();        int len = kingdom.length;        int basicCost = 0;        // create edges with cost        for (int i = 0; i < len; i++)        {            for (int j = i+1; j < len; j++)            {                Edge edge = new Edge();                edge.a = i; edge.b = j;                if (kingdom[i].charAt(j) == '0')                {                    edge.cost = getValue(build, i, j);                }                else                {                    int tmp = getValue(destroy, i, j);                    basicCost += tmp;                    edge.cost = -tmp;                }                edges.add(edge);            }        }        // Kruskal algo        Collections.sort(edges);        int[] color = new int[len];        for (int i = 0; i < len; i++)        {            color[i] = i;        }        int cost = basicCost;        for (int i = 0; i < edges.size(); i++)        {            Edge e = edges.get(i);            if (color[e.a] == color[e.b]) continue;            cost += e.cost;            int oldColor = color[e.a];            for (int k = 0; k < len; k++)            {                if (color[k] == oldColor)                {                    color[k] = color[e.b];                }            }        }        return cost;    }        private int getValue(String[] costs, int i, int j)    {        char c = costs[i].charAt(j);        if (c >= 'A' && c <= 'Z')        {            return c - 'A';        }        else             return c - 'a' + 26;    }}class Edge implements Comparable
       
        {    public int a;    public int b;    public int cost;    public int compareTo(Edge rhs)    {        return this.cost - rhs.cost;    }}