本文共 1369 字，大约阅读时间需要 4 分钟。
题意：龙要制作n个茶，每个茶的配方是一个字符串，两个字符串之间有一个差值，这个差值为两个字符串每个对应字母之间差的绝对值的最大值，求制作所有茶时获得的所有差值中的最大值。
解法：克鲁斯卡尔。将茶的配方作为点，将每两个点之间的差值作为边权，求最小生成树，这棵树中最大的边即为答案。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long longusing namespace std;string s[1005];int cal(int i, int j){ int res = 0; for(int k = 0; k < s[i].size(); k++) res = max(res, abs(s[i][k] - s[j][k])); return res;}struct node{ int u, v; int val; node(int u, int v, int val) : u(u), v(v), val(val) {} node() {} bool operator < (const node &tmp) const { return val < tmp.val; }};vector edge;int father[1005];int Find(int a){ if(a != father[a]) father[a] = Find(father[a]); return father[a];}int main(){ int n, m; while(~scanf("%d%d", &n, &m)) { for(int i = 0; i < 1005; i++) father[i] = i; for(int i = 0; i < n; i++) { cin >> s[i]; } for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) { edge.push_back(node(i, j, cal(i, j))); } int ans = 0; sort(edge.begin(), edge.end()); int len = edge.size(); for(int i = 0; i < len; i++) { int a = Find(edge[i].u), b = Find(edge[i].v); if(a != b) { father[a] = b; ans = edge[i].val; } } printf("%d\n", ans); } return 0;}
转载于:https://www.cnblogs.com/Apro/p/4685997.html