Zepto Code Rush 2014:http://codeforces.com/problemset/problem/436/C
题意：k个点，每个点都是一个n * m的char型矩阵。对与每个点，权值为n * m或者找到一个之前的点，取两个矩阵对应位置不同的字符个数乘以w。找到一个序列，使得所有点的权值和最小。
题解：很明显的最小生成树。但是要加入一个0点，边权为n*m,其余k个点两两建立一条边，边权是diff[i][j]*w，最后这一题，我要死掉的地方就是输出，不仅要输出费用，还要输出边，但是这里的边，看了半天，才知道，要按dfs序列输出，并且第一个点的前一个点必须是0.哎，这一题，只能说明自己太渣了。有点伤心。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,k,w,num,cost,ct;
int fa[];
int g[][];
void init(){
for(int i=;i<=k;i++)
fa[i]=i;
}
int Find(int x){
int s;
for(s=x;s!=fa[s];s=fa[s]);
while(s!=x){
int temp=fa[x];
fa[x]=s;
x=temp;
}
return s;
}
struct Node{
int x;
int y;
int val;
}edge[];
int cmp1(Node a,Node b){
return a.val<b.val;
}
int cmp2(Node a,Node b){
return a.y<b.y;
}
char mp[][][];
void deal(){
for(int i=;i<=k;i++){
for(int j=i+;j<=k;j++){
int counts=;
for(int g=;g<=n;g++){
for(int h=;h<=m;h++){
if(mp[i][g][h]!=mp[j][g][h])
counts++;
}
}
edge[++num].x=i;
edge[num].y=j;
edge[num].val=counts*w;
}
}
for(int i=;i<=k;i++){
edge[++num].x=;
edge[num].y=i;
edge[num].val=n*m;
}
}
void print(int u,int fa){
for(int i=;i<=k;i++){
if(g[u][i]>=&&i!=fa){
printf("%d %d\n",i,u);
print(i,u);
}
} }
int main(){
while(~scanf("%d%d%d%d",&n,&m,&k,&w)){
init();
memset(g,-,sizeof(g));
for(int i=;i<=k;i++){
for(int j=;j<=n;j++){
for(int h=;h<=m;h++)
cin>>mp[i][j][h];
}
}
num=;
deal();
sort(edge+,edge+num+,cmp1);
ct=;cost=;
for(int i=;i<=num;i++){
int x=Find(edge[i].x);
int y=Find(edge[i].y);
if(x!=y){
fa[x]=y;
int tx=edge[i].y;
int ty=edge[i].x;
g[tx][ty]=g[ty][tx]=edge[i].val;
ct++;
cost+=edge[i].val;
}
if(ct==k)break;
}
printf("%d\n",cost);
print(,);
}
}