点击打开链接
这道题一开始纠结于谁才是祖先 想到最短路上去了.. 其实与祖先是谁无关 与两点之间谁衍生出谁亦无关 因为在一颗树中谁当根节点不都一样吗
其实就是从n(n-1)/2条边的完全图中找最小生成树 两种类型之间的差异度就是两点之间边的权值
#include <stdio.h> #include <algorithm> using namespace std; struct node { int u; int v; int w; }; struct node edge[1999001]; int f[2001]; int n,m; char type[2001][8]; int cmp(node n1,node n2) { return n1.w<n2.w; } int unite(int u,int v); int getf(int p); int main() { int i,j,k,cnt,sum; while(scanf("%d",&n)!=EOF) { if(n==0) break; for(i=1;i<=n;i++) { scanf("%s",type[i]); } m=0; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { sum=0; for(k=0;k<7;k++) { if(type[i][k]!=type[j][k]) { sum++; } } m++; edge[m].u=i; edge[m].v=j; edge[m].w=sum; } } sort(edge+1,edge+m+1,cmp); for(i=1;i<=n;i++) { f[i]=i; } cnt=0,sum=0; for(i=1;i<=m;i++) { if(unite(edge[i].u,edge[i].v)) { cnt++,sum+=edge[i].w; } if(cnt==n-1) { break; } } printf("The highest possible quality is 1/%d.\n",sum); } return 0; } int unite(int u,int v) { int fu,fv; fu=getf(u); fv=getf(v); if(fu!=fv) { f[fv]=fu; return 1; } else return 0; } int getf(int p) { if(f[p]==p) return p; else { f[p]=getf(f[p]); return f[p]; } }
