도 론 알고리즘 (4) - TSP 여행사 문제 최 단 회로 구하 기 (acm)
행렬 의 개선 에 대해 우 리 는 행렬 에 대한 처 리 는 모든 줄 에서 행 의 최소 치 를 빼 고 각 열 에서 열 의 최소 치 를 빼 고 이 최소 치 를 결과 sum 에 추가 하 는 것 입 니 다. 이러한 조작 은 행렬 을 희소 화 하 는 개선 (주의, 희소 화 된 행렬 이 반드시 희소 행렬 이 아니 라 헷 갈 리 지 마 세 요) 입 니 다. 나머지 행렬 에서 dfs 검색 을 합 니 다.검색 공간 을 낮 추고 검색 한 결 과 를 sum 에 추가 하 는 것 이 최종 결과 입 니 다.개 선 된 행렬 은 다시 반복 적 으로 개선 할 수 없습니다. 즉, 모든 줄 의 모든 열 에서 최소 치 를 뺀 작업 은 한 번 만 할 수 있 습 니 다. 왜 그런 지 에 대해 서 는 문제 가 있 으 면 메 시 지 를 환영 합 니 다.
코드 첨부:
#include
#define MAX 0x7fffffff
int g[16][16],visit[16],n,ans=MAX,count=1,sum=0;
void dfs(int i,int count,int sum)
{
int p;
if(sum>=ans)return;
if(count==n)
{
sum+=g[i][1];
ans=ans>sum?sum:ans;
return;
}
for(p=1;p<=n;p++)
{
if(!visit[p]&&p!=i)
{
visit[i]=1;
dfs(p,count+1,sum+g[i][p]);
visit[i]=0;
}
}
}
int main()
{
int i,j,min;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
min=MAX;
for(j=1;j<=n;j++)
{
scanf("%d",&g[i][j]);
if(j!=i&&min>g[i][j])min=g[i][j];
}
if(min!=MAX)
{
sum+=min;
for(j=1;j<=n;j++)if(j!=i)g[i][j]-=min;
}
}
for(j=1;j<=n;j++)
{
min=MAX;
for(i=1;i<=n;i++)if(i!=j&&min>g[i][j])min=g[i][j];
if(min!=MAX)
{
sum+=min;
for(i=1;i<=n;i++)if(i!=j)g[i][j]-=min;
}
}
visit[1]=1;
dfs(1,1,sum);
printf("%d
",ans);
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
