poj 1789 트럭 역사 (kruskal 알고리즘)
3969 단어 history
사고: 하나의 점, 두 줄 사이 에 문자 의 개 수 를 모 르 면 가중치 로 간주한다.그리고 kruskal 알고리즘 으로 최소 생 성 트 리 를 계산 합 니 다.
나 는 두 개의 코드 를 썼 다. 하 나 는 우선 대기 열 로 쓴 것 이다.그런데 시간 이 초과 됐어 요. 왜 그런 지 모 르 겠 어 요.누 군가 풀 어 줬 으 면 좋 겠 어 요.뒤에 사용 할 배열 sort 정렬 하고 AC.
code:
배열 sort 정렬 AC 코드:
#include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
struct edge
{
int from;
int to;
int cost;
};
bool cmp(edge e1,edge e2)
{
return e1.cost<e2.cost;
}
edge node[2001*2001];
int father[2005];
int nn,n;
int find(int x) //
{
if(x!=father[x])
{
father[x]=find(father[x]);
}
return father[x];
}
void kruskal()
{
int MST=0;
for(int i=0;i<2005;i++)
{
father[i]=i;
}
for(int i=0;i<nn;i++)
{
int fx=find(node[i].from);
int fy=find(node[i].to);
if(fx!=fy)
{
father[fx]=fy;
MST+=node[i].cost;
}
}
printf("The highest possible quality is 1/%d.
",MST);
}
int main()
{
char str[2005][10];
int i,j;
while(scanf("%d",&n)==1&&n)
{
nn=0;
for(i=0;i<n;i++)
{
scanf("%s",str[i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
int sum=0;
for(int kk=0;kk<7;kk++)
{
if(str[i][kk]!=str[j][kk])
{
sum++;
}
}
node[nn].from=i;
node[nn].to=j;
node[nn].cost=sum;
nn++;
}
}
sort(node,node+nn,cmp);
kruskal();
}
return 0;
}
우선 대기 열 시간 초과 코드#include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
struct edge
{
friend bool operator<(edge e1,edge e2)
{
return e1.cost>e2.cost;
}
int from;
int to;
int cost;
};
edge e;
priority_queue<edge> Q;
int father[2005];
int nn,n;
int find(int x)
{
if(x!=father[x])
{
father[x]=find(father[x]);
}
return father[x];
}
void kruskal()
{
int MST=0;
for(int i=0;i<2005;i++)
{
father[i]=i;
}
int num=0;
while(!Q.empty()&&num!=nn)
{
edge e=Q.top();
//printf("BBB%d %d %d
",e.from,e.to,e.cost);
Q.pop();
int fx=find(e.from);
int fy=find(e.to);
if(fx!=fy)
{
father[fx]=fy;
MST+=e.cost;
num++;
}
}
printf("The highest possible quality is 1/%d.
",MST);
}
int main()
{
char str[2005][10];
int i,j;
while(scanf("%d",&n)==1&&n)
{
nn=0;
while(!Q.empty()) Q.pop();
for(i=0;i<n;i++)
{
scanf("%s",str[i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
int sum=0;
for(int kk=0;kk<7;kk++)
{
if(str[i][kk]!=str[j][kk])
{
sum++;
}
}
nn++;
e.from=i;
e.to=j;
e.cost=sum;
Q.push(e);
//printf("edge:%d %d %d %d
",e.from,e.to,e.cost,nn);
}
}
kruskal();
}
return 0;
}
저작권 성명: 본 블 로그 의 오리지널 글, 블 로그, 동의 없 이 전재 할 수 없습니다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
노해가 아니라고 생각했던 기술, 의외로 곧 노해가 되는 것 무서워이 기사는 주관 9할 9분입니다. 이론은 어떤 사람은 있다고 생각하기 때문에 꼭 코멘트를 (웃음) 최근 월간 I/O가 아직 살아있는 것을 알고 정기 구독을 시작해 보았습니다. (゚Д゚)オォォ... 라는 느낌입니다. ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.