題意：
? ? ? 給你一些車牌號，然后另一兩個車牌號之間的權值就是這兩個字符串之間相同位置不同字母的個數(shù)，然后求最小生成樹。


思路：
? ? ? 裸題，不解釋了。


#include<stdio.h>
#include<algorithm>


using namespace std;


typedef struct
{
? ? int a ,b ,c;
}EDGE;


EDGE edge[2000*2000/2+10];
int mer[2000+5];
char str[2000+5][10];




bool camp(EDGE a ,EDGE b)
{
? ? return a.c < b.c;
}


int finds(int x)
{
? ? return x == mer[x] ? x : mer[x] = finds(mer[x]);
}


int main ()
{
? ? int n ,i ,j ,ans;
? ? while(~scanf("%d" ,&n) && n)
? ? {
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? scanf("%s" ,str[i]);
? ? ? ? int nowid = 0;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? for(j = i + 1 ;j <= n ;j ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? ++nowid;
? ? ? ? ? ? ? ? edge[nowid].c = 0;
? ? ? ? ? ? ? ? edge[nowid].a = i ,edge[nowid].b = j;
? ? ? ? ? ? ? ? for(int k = 0 ;k < 7 ;k ++)
? ? ? ? ? ? ? ? if(str[i][k] != str[j][k])
? ? ? ? ? ? ? ? edge[nowid].c ++;
? ? ? ? ? ? }
? ? ? ? ? ? mer[i] = i;
? ? ? ? }
? ? ? ? sort(edge + 1 ,edge + nowid + 1 ,camp);
? ? ? ? ans = 0;
? ? ? ? for(i = 1 ;i <= nowid ;i ++)
? ? ? ? {
? ? ? ? ? ? int x = finds(edge[i].a);
? ? ? ? ? ? int y = finds(edge[i].b);
? ? ? ? ? ? if(x == y) continue;
? ? ? ? ? ? ans += edge[i].c;
? ? ? ? ? ? mer[x] = y;
? ? ? ? }
? ? ? ? printf("The highest possible quality is 1/%d.\n" ,ans);
? ? }
? ? return 0;


}

總結

以上是生活随笔為你收集整理的POJ1789简单小生成树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。