poj1789 Kruskal 알고리즘, TLE 7번, 어쩔 수 없이 코드를 복제합니다.참조 후에도 TLE, 불신, 제출 부착, 750MS 통과
2040 단어 kruskal 알고리즘tlepoj1789
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
#define MAX 2005
char str[MAX][8];
int n,father[MAX],rank[MAX],k;//k
struct node{
int st;
int en;
int we;
}edge[MAX*MAX/2];
/*bool cmp1(node a,node b)
{
return a.we<b.we;
}*/
int cmp(const void *a,const void *b)
{
return ((node*)a)->we-((node*)b)->we;
}
int Weight(int i,int j)
{
int m=0;
int w=0;
while(m<7)
{
if(str[i][m]!=str[j][m])
w++;
m++;
}
return w;
}
//
void make_set()
{
int i;
for(i=0; i<MAX; i++)
{
father[i]=i;
rank[i]=0;
}
}
int find_set(int x)
{
if(father[x]!=x)
father[x]=find_set(father[x]);
return father[x];
}
bool Union(int x,int y)
{
int px=find_set(x);
int py=find_set(y);
if(px!=py)
{
if(rank[px]>rank[py])
{
father[py]=px;
}
else
{
if(rank[px]==rank[py])
rank[py]++;
father[px]=py;
}
return true;
}
return false;
}
int Kruskal()
{
int i,cost=0,nCount=0;
for(i=0; i<k; i++)
{
int start,end;
start=edge[i].st;
end=edge[i].en;
if(Union(start,end))
{
cost+=edge[i].we;
}
}
return cost;
}
int main()
{
int i,j;
//freopen("acm.txt","r",stdin);
while(scanf("%d",&n)!=EOF && n)
{
make_set();
getchar();
for(i=0; i<n; i++)
{
scanf("%s",str[i]);
}
k=0;
for(i=0; i<n-1; i++)
{
for(j=i+1; j<n; j++)
{
edge[k].st=i;
edge[k].en=j;
edge[k++].we=Weight(i,j);
}
}
//sort(edge,edge+k,cmp1);
qsort(edge,k,sizeof(node),cmp);
printf("The highest possible quality is 1/%d.
",Kruskal());
}
return 0;
}