http://community.topcoder.com/stat?c=problem_statement&pm=11282&rd=14724
这道题是最小生成树，但怎么转化是关键。首先是把所有的路都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<Edge> edges = new ArrayList<Edge>();
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<Edge>
{
public int a;
public int b;
public int cost;
public int compareTo(Edge rhs)
{
return this.cost - rhs.cost;
}
}