题目描述：给你k个n*m个矩阵 里面有不同的字母，每个图形可以用前面已有的矩阵变化过来（起初没有），花费是相同点不同字母的个数*w，或者全部赋值花费n*m*w;
问生成全部矩阵最少花费多少。
分析：把它构造成一个完全图，点是矩阵，边即两个举证之间的花费，所以问题转化为求最小生成树，注意dfs遍历树的时候只需要不走到父节点就行了，并不用标记所有点。
ac代码： 
#include<bits/stdc++.h>
using namespace std;
struct Edge {
    int u,v,w;
}edge[1100*1100];
bool cmp(Edge a,Edge b){
    return a.w<b.w;
}
int n,m,k,w;
int fa[1100],diff[1100][1100];
char ch[1100][20][20];
vector <int >vc[1100];
int get_diff(char a[][20],char b[][20]){
    int ret=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(a[i][j]!=b[i][j]) ret++;
    return ret;
}
int getfa(int x){
    if(fa[x]!=x)return fa[x]=getfa(fa[x]);
     else return fa[x];
}
int Kruscal(int eg){
    sort(edge,edge+eg,cmp);
    for(int i=0;i<=k+1;i++){
        fa[i]=i;
        vc[i].clear();
    }
    int cnt=k+1,ans=0;
    for(int i=0;i<eg;i++){
        int f1=getfa(edge[i].u);
        int f2=getfa(edge[i].v);
        if(f1!=f2){
            fa[f1]=f2;
            ans+=edge[i].w;
            vc[edge[i].u].push_back(edge[i].v);
            vc[edge[i].v].push_back(edge[i].u);
            cnt--;
            if(cnt==1) break;
        }
    }
    return ans;
}
void dfs(int u,int fa){
    for(int i=0,sz=vc[u].size();i<sz;i++){
        int v=vc[u][i];
        if(v!=fa){
            cout<<v<<' '<<u<<endl;
            dfs(v,u);
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
//    freopen("1.txt","r",stdin);
    cin>>n>>m>>k>>w;
    for(int i=1;i<=k;i++)
        for(int j=0;j<n;j++)
            cin>>ch[i][j];
    for(int i=1;i<=k;i++)
        for(int j=i+1;j<=k;j++)
            diff[j][i]=diff[i][j]=get_diff(ch[i],ch[j])*w;
    int eg=0;
    for(int i=1;i<=k;i++){
        edge[eg++]=(Edge){0,i,n*m};
        for(int j=i+1;j<=k;j++)
            edge[eg++]=(Edge){i,j,diff[i][j]};
    }
    cout<<Kruscal(eg)<<endl;
    dfs(0,0);
}