【アルゴリズム】最小生成ツリーのprim
4004 ワード
1.primアルゴリズム
ソースコードには、非アクセスノードiからアクセスノードセットまでの最短距離をlowcost[i]で記録する.primアルゴリズムはDijkstraアルゴリズムと非常に類似しており,緩和時に緩和条件が異なる.
2.質問
2.1 POJ 1258
ソースコード
2.2 POJ 1789
構想:まず2つのtruck type間の距離を得て、完全図を確立して、最小生成ツリーの経路の和を計算します.
ソース:
2.3 POJ 2421
構想:確立された道路の重み値を0とマークします.
ソース:
2421
Accepted
204K
0MS
C
1075B
2013-03-01 20:43:58
ソースコードには、非アクセスノードiからアクセスノードセットまでの最短距離をlowcost[i]で記録する.primアルゴリズムはDijkstraアルゴリズムと非常に類似しており,緩和時に緩和条件が異なる.
2.質問
2.1 POJ 1258
ソースコード
#include "stdio.h"
#include "stdlib.h"
#define MAX 100
int farm[MAX][MAX]={0};
void init(int N)
{
int i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
scanf("%d",&farm[i][j]);
}
void prim(int N)
{
int i,count=1,sum=0,min_node,min_lowcost;
int *lowcost=(int *) malloc(N*sizeof(int));
int *visit=(int *) malloc(N*sizeof(int));
for(i=0;i<N;i++)
{
lowcost[i]=farm[0][i];
visit[i]=0;
}
visit[0]=1;
while(count<=N-1)
{
min_lowcost=100001;
min_node=0;
for(i=1;i<N;i++)
{
if(lowcost[i]<min_lowcost&&visit[i]==0)
{
min_lowcost=lowcost[i];
min_node=i;
}
}
visit[min_node]=1;
sum+=lowcost[min_node];
for(i=1;i<N;i++)
{
if(farm[min_node][i]!=0&&farm[min_node][i]<lowcost[i]&&visit[i]==0)
lowcost[i]=farm[min_node][i];
}
count++;
}
printf("%d
",sum);
free(lowcost);
free(visit);
}
int main()
{
int N;
while(~scanf("%d",&N))
{
init(N);
prim(N);
}
return 0;
}
2.2 POJ 1789
構想:まず2つのtruck type間の距離を得て、完全図を確立して、最小生成ツリーの経路の和を計算します.
ソース:
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define MAX 2000
#define inf 0xffff
char truck_type[MAX][7];
int dis_graph[MAX][MAX]={inf};
int get_dis(char a[],char b[])
{
int i,distance=0;
for(i=0;i<7;i++)
{
if(a[i]!=b[i])
distance++;
}
return distance;
}
void prim(int n)
{
int i,count=1,Q=0,min_node=0,min_lowcost;
int *lowcost=(int *)malloc(n*sizeof(int));
int *visit=(int *) malloc(n*sizeof(int));
for(i=0;i<n;i++)
lowcost[i]=dis_graph[0][i];
memset(visit,0,n*sizeof(int));
visit[0]=1;
while(count<=n-1)
{
min_lowcost=8;
for(i=1;i<n;i++)
{
if(lowcost[i]<min_lowcost&&visit[i]==0)
{
min_lowcost=lowcost[i];
min_node=i;
}
}
visit[min_node]=1;
Q+=lowcost[min_node];
for(i=1;i<n;i++)
{
if(dis_graph[min_node][i]<lowcost[i]&&visit[i]==0)
lowcost[i]=dis_graph[min_node][i];
}
count++;
}
free(lowcost);
free(visit);
printf("The highest possible quality is 1/%d.
",Q);
}
int main()
{
int i,j,n;
while(scanf("%d",&n)&&n)
{
for(i=0;i<n;i++)
scanf("%s",truck_type[i]);
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
dis_graph[i][j]=dis_graph[j][i]=get_dis(truck_type[i],truck_type[j]);
prim(n);
}
return 0;
}
2.3 POJ 2421
構想:確立された道路の重み値を0とマークします.
ソース:
2421
Accepted
204K
0MS
C
1075B
2013-03-01 20:43:58
#include "stdio.h"
#include "stdlib.h"
#define MAX 100
int road[MAX][MAX]={0};
void init(int N)
{
int a,b,i,j,Q;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
scanf("%d",&road[i][j]);
scanf("%d",&Q);
for(i=0;i<Q;i++)
{
scanf("%d%d",&a,&b);
road[a-1][b-1]=road[b-1][a-1]=0;
}
}
void prim(int N)
{
int i,count=1,sum=0,min_node,min_lowcost;
int *lowcost=(int *) malloc(N*sizeof(int));
int *visit=(int *) malloc(N*sizeof(int));
for(i=0;i<N;i++)
{
lowcost[i]=road[0][i];
visit[i]=0;
}
visit[0]=1;
while(count<=N-1)
{
min_lowcost=1001;
min_node=0;
for(i=1;i<N;i++)
if(lowcost[i]<min_lowcost&&visit[i]==0)
{
min_lowcost=lowcost[i];
min_node=i;
}
visit[min_node]=1;
sum+=lowcost[min_node];
for(i=1;i<N;i++)
if(road[min_node][i]<lowcost[i]&&visit[i]==0)
lowcost[i]=road[min_node][i];
count++;
}
printf("%d",sum);
free(lowcost);
free(visit);
}
int main()
{
int N;
while(~scanf("%d",&N))
{
init(N);
prim(N);
}
return 0;
}