首先要强调一点 这不是一道ACM题,这是他妹的一道英语阅读理解。
题意:输入N 代表有N种汽车。每两种汽车之间有一条边,边的权值的定义为 两串字符串之间有几个不同的字母。。。稠密图。。。。普利姆 或者 克鲁斯卡尔 + 路径压缩
我认为后者能通吃所以很无耻的不会第一种。。。。。
1 #include <iostream> 2 #include <algorithm> 3 #include <cmath> 4 #include <cstdio> 5 #include <cstring> 6 #include <cstdlib> 7 #include <queue> 8 9 using namespace std; 10 11 char s[2010][10]; 12 13 struct E 14 { 15 int u,v,w; 16 }edge[4000100]; 17 18 bool cmp(E a,E b) 19 { 20 return a.w < b.w; 21 } 22 23 int mark[2010]; 24 25 int Min; 26 27 int find(int x) 28 { 29 int k,j,r; 30 r = x; 31 while(r != mark[r]) 32 r = mark[r]; 33 k = x; 34 while(k != r) 35 { 36 j = mark[k]; 37 mark[k] = r; 38 k = j; 39 } 40 return r; 41 } 42 43 void merge(int top) 44 { 45 int i; 46 int fu,fv; 47 for(i = 0;i < top; i++) 48 { 49 50 fu = find(edge[i].u); 51 fv = find(edge[i].v); 52 53 if(fu != fv) 54 { 55 Min += edge[i].w; 56 mark[fu] = fv; 57 } 58 } 59 printf("The highest possible quality is 1/%d. ",Min); 60 } 61 62 int main() 63 { 64 int n,i,j,k,top,sum; 65 66 while(scanf("%d",&n) && n) 67 { 68 for(i = 0;i < n; ++i) 69 scanf("%s",s[i]); 70 71 for(i = 0;i < n; ++i) 72 mark[i] = i; 73 74 for(i = 0,top = 0;i < n; ++i) 75 for(j = i+1;j < n; ++j) 76 { 77 for(sum = 0,k = 0;k < 7; k++) 78 if(s[i][k] != s[j][k]) 79 ++sum; 80 edge[top].u = i; 81 edge[top].v = j; 82 edge[top].w = sum; 83 ++top; 84 } 85 sort(edge,edge+top,cmp); 86 87 Min = 0; 88 merge(top); 89 } 90 return 0; 91 }
再谈路径压缩
递归和非递归两种方式
递归:
int find(int x) //查找x元素所在的集合,回溯时压缩路径
{
if (x != parent[x])
{
parent[x] = find(parent[x]); //回溯时的压缩路径
} //从x结点搜索到祖先结点所经过的结点都指向该祖先结点
return parent[x];
}
显然当我们需要用路径压缩的时候 递归方法也很容易溢出。。。。。。
非递归:
1 int find(int x) 2 { 3 int k, j, r; 4 r = x; 5 while(r != parent[r]) //查找跟节点 6 r = parent[r]; //找到跟节点,用r记录下 7 k = x; 8 while(k != r) //非递归路径压缩操作 9 { 10 j = parent[k]; //用j暂存parent[k]的父节点 11 parent[k] = r; //parent[x]指向跟节点 12 k = j; //k移到父节点 13 } 14 return r; //返回根节点的值 15 }