• 题意：
  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
      
        G[maxn];int in[maxn];vector
       
         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;}