题意:龙要制作n个茶,每个茶的配方是一个字符串,两个字符串之间有一个差值,这个差值为两个字符串每个对应字母之间差的绝对值的最大值,求制作所有茶时获得的所有差值中的最大值。
解法:克鲁斯卡尔。将茶的配方作为点,将每两个点之间的差值作为边权,求最小生成树,这棵树中最大的边即为答案。
代码:
#include<stdio.h> #include<iostream> #include<algorithm> #include<string> #include<string.h> #include<math.h> #include<limits.h> #include<time.h> #include<stdlib.h> #include<map> #include<queue> #include<set> #include<stack> #include<vector> #define LL long long using 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 <node> 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 ", ans); } return 0; }