HDU的最小數題目:
1301
1233
1863
1162
1879
1875
昨天就一直在做這類題目，但一直以為是最短路，其實很像
我昨天的做法其實就是prime算法
以
http://acm.hdu.edu.cn/showproblem.php?pid=1233為例子
#include<stdio.h>
#define inf 0x7FFFFFFF
#define M 100
int map[M][M];
int link[M];
bool visit[M];
int main()
{
int n,m,a,b,i,j,dis,min,cnt;
while (scanf("%d",&n),n)
{
for(i=1;i<=n;i++)
{
visit[i] = 1;
for(j=1;j<=n;j++)
map[i][j] = inf;
}
m = n*(n-1)/2;
while(m--)
{
scanf("%d%d%d",&a,&b,&dis);
map[a][b] = map[b][a] = dis;
}
cnt = 1;
link[0] = 1;
visit[1] = 0;
dis = 0;
while(cnt != n)
{
min = inf;
for(i=0;i<cnt;i++)
for(j=1;j<=n;j++)
{
if(visit[j] && map[ link[i] ][j]<min)
{
link[cnt] = j;
min = map[ link[i] ][j];
}
}
dis += min;
visit[link[cnt]] = 0;
cnt ++;
}
printf("%d\n",dis);
}
return 0;
}
今天學習了
Kruskal，快捷很多，也就是 大大說講的并查集寫的，不經效率高，寫的也快
#include<stdio.h>
#include<stdlib.h>
#define M 101
struct L{
int a,b,dis;
}road[M*(M-1)/2];
int x[M];
int find(int a)
{
int t,b=a;
while(a!=x[a])
a = x[a];
while(b!=a)
{
t = x[b];
x[b] = a;
b = t;
}
return a;
}
int cmp(const void *a,const void *b)
{
return (*(struct L *)a).dis - (*(struct L *)b).dis;
}
int main()
{
int n,m,i,dis,cnt,a,b;
while (scanf("%d",&n),n)
{
m = n*(n - 1)/2;
for(i=1;i<=n;i++)
x[i] = i;
for(i=0;i<m;i++)
scanf("%d%d%d",&road[i].a,&road[i].b,&road[i].dis);
qsort(load,m,sizeof(road[0]),cmp);
dis = 0;
cnt = 0;
for(i=0;cnt<n-1;i++)
{
a = find(road[i].a);
b = find(road[i].b);
if(a!=b)
{
dis += road[i].dis;
x[a] = b;
cnt ++;
}
}
printf("%d\n",dis);
}
return 0;
}
posted on 2009-02-16 11:18
shǎ崽 閱讀(926)
評論(0) 編輯 收藏 引用