题目链接
- 题意：
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;elsecout << 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;
}