- 题意：
k个点，每一个点都是一个n * m的char型矩阵。对与每一个点，权值为n * m或者找到一个之前的点，取两个矩阵相应位置不同的字符个数乘以w。找到一个序列，使得全部点的权值和最小 - 分析：
首先，这个图是一个无向图。求权值和最小，每一个权值相应的是一条边，且每一个点仅仅能有一个权值即一条边，一个k个边，和生成树非常像，可是须要证明不能有环形。最好还是如果如今有三个点，每一个点的最小边成环，这时候是不能找到一个序列使得每一个点都取到它的最小边值的，所以，k个点k个边不能有环且边值和最小，就是最小生成树。
prim算法：
const int maxn = 1100; char ipt[maxn][11][11];
int dist[maxn][maxn];
int d[maxn], p[maxn];
bool vis[maxn];
int n, m, k, w; int main()
{
// freopen("in.txt", "r", stdin);
while (~RIV(n, m, k, w))
{
CLR(dist, 0);
REP(i, k)
{
vis[i] = false;
d[i] = n * m;
p[i] = -1;
} REP(i, k) REP(j, n)
RS(ipt[i][j]);
REP(i, k) REP(j, k) REP(ii, n) REP(jj, m)
dist[i][j] += (ipt[i][ii][jj] != ipt[j][ii][jj]) * w;
d[0] = 0;
int sum = n * m;
VI ans;
REP(i, k)
{
int M = INF, ind;
REP(j, k)
if (!vis[j] && d[j] < M)
{
ind = j;
M = d[j];
}
vis[ind] = true;
sum += M;
ans.push_back(ind);
REP(j, k)
{
if (!vis[j] && dist[ind][j] < d[j])
{
d[j] = dist[ind][j];
p[j] = ind;
}
}
}
WI(sum);
REP(i, ans.size())
{
cout << ans[i] + 1 << ' ' << p[ans[i]] + 1 << endl;
}
}
return 0;
}
kruskal：
const int maxn = 1100; struct Edge
{
int from, to, dist;
int operator< (const Edge& rhs) const
{
return dist < rhs.dist;
}
Edge (int from = 0, int to = 0, int dist = 0)
{
this->from = from;
this->to = to;
this->dist = dist;
}
}; vector<Edge> G[maxn];
int in[maxn];
vector<Edge> edges;
int fa[maxn];
char ipt[maxn][105];
int diff[maxn][maxn];
int n, m, k, w;
int find(int n)
{
return (n == fa[n]) ? n : (fa[n] = find(fa[n]));
}
void init(int n)
{
REP(i, n)
{
fa[i] = i;
G[i].clear();
in[i] = 0;
}
edges.clear();
}
void AddEdge(int u, int v, int dist)
{
edges.push_back(Edge(u, v, dist));
}
void dfs(int u, int fa)
{
REP(i, G[u].size())
{
Edge& e = G[u][i];
if (e.to != fa)
{
if (e.dist == m * n)
cout << e.to + 1 << ' ' << 0 << endl;
else
cout << e.to + 1 << ' ' << u + 1 << endl;
dfs(e.to, u);
}
}
}
void solve()
{
int ret = 0;
sort(all(edges));
REP(i, edges.size())
{
Edge& e = edges[i];
int ru = find(e.from), rv = find(e.to);
if (ru != rv)
{
fa[ru] = rv;
ret += e.dist;
G[e.from].push_back(Edge(e.from, e.to, e.dist));
G[e.to].push_back(Edge(e.to, e.from, e.dist));
in[e.from]++;
in[e.to]++;
}
}
WI(ret + n * m);
REP(i, k)
{
if (in[i] <= 1)
{
cout << i + 1 << ' ' << 0 << endl;
dfs(i, -1);
break;
}
}
} int judge(int a, int b)
{
int cnt = 0;
REP(i, n * m)
cnt += (ipt[a][i] != ipt[b][i]);
return cnt;
} int main()
{
// freopen("in.txt", "r", stdin);
while (~RIV(n, m, k, w))
{
CLR(diff, 0);
REP(i, k)
{
int len = 0;
REP(j, n)
{
RS(ipt[i] + len);
len = strlen(ipt[i]);
}
}
REP(i, k) REP(j, k) REP(t, n * m)
diff[i][j] += (ipt[i][t] != ipt[j][t]);
init(k);
REP(i, k) REP(j, k)
{
if (i == j)
continue;
AddEdge(i, j, min(diff[i][j] * w, n * m));
}
solve();
}
return 0;
}