poj-1151 Highways
http://poj.org/problem?id=1751
最小生成ツリーの簡単な応用
最小生成ツリーの簡単な応用
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stack>
#include <queue>
using namespace std;
#define INF 10000000
double map[1110][1110],dis[1110];
int n,m,v[1110],pre[1010],a,b,c,d[1110];
struct node
{
double x,y;
}p[1010];
double makedis(int i,int j)
{
return sqrt( 1.0*(p[i].x - p[j].x)*(p[i].x - p[j].x) + 1.0*(p[i].y - p[j].y)*(p[i].y - p[j].y));
}
void prim()
{
int i, j, k;
double min, sum = 0;memset(v, 0, sizeof(v));
for (i = 1; i <= n; i++)
{
dis[i] = map[1][i];
pre[i] = 1;
}
v[1] = 1;dis[1] = 0;pre[1]= - 1;
for (i = 2; i <= n; i++)
{
k = 1;
min = INF;
for (j = 1; j <= n; j++)
if (!v[j] && min>dis[j])
{
k = j;
min = dis[j];
}
sum += min;
v[k] = 1;
if (min !=0 )
cout<<pre[k]<<" "<<k<<endl;
for (j = 1; j <= n; j++)
if (!v[j] && dis[j]>map[k][j])
{
dis[j] = map[k][j];
pre[j] = k;
}
}
}
int main()
{
scanf("%d",&n);
{
for(int i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
for(int i=1;i<=n;i++)
for(int j = 1;j<=n;j++)
{
if (i == j)
map[i][j] = 0;
else
map[i][j] = INF;
}
for(int i=1;i<=n;i++)
for(int j = 1;j<=n;j++)
{
if (map[i][j] > makedis(i,j))
{
map[i][j] = makedis(i,j);
map[j][i] = makedis(i,j);
}
}
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&a,&b);
map[a][b] = map[b][a] = 0;
}
prim();
}
return 0;
}