poj 1751 Highways MST

简介:

   水到家的一道题,居然WA了3次……没注意到距离是double……没有输出的话要输出一行空行 


/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define INF 1E9
using namespace std;
double d[751];
double dis[751][751];
bool vis[751];
int near[751];
struct node
{
    int x,y;
};
node org[751];
int n;
int prim()
{
    double Min,ans=0;
    int K=n,i,t,now=0;
    while(K--)
    {
        Min=INF;
        for(i=0;i<n;i++)
            if(!vis[i]&&d[i]<Min)
                Min=d[i],now=i;
        vis[now]=1;
        if(now)
        {
            ans+=Min;
            if(Min)printf("%d %d\n",now+1,near[now]+1);
        }
        for(i=0;i<n;i++)
        {
            if(vis[i]||d[i]<=dis[now][i])continue;
            d[i]=dis[now][i];near[i]=now;
        }
    }
    return ans;
}
int main()
{
    int i,j,m,a,b,T=0;
    while(~scanf("%d",&n))
    {
        memset(vis,0,sizeof(vis));
        memset(d,127,sizeof(d));
        for(i=0;i<n;i++)
          scanf("%d%d",&org[i].x,&org[i].y);
        for(i=0;i<n;i++)
         for(j=0;j<=i;j++)
             dis[j][i]=dis[i][j]=sqrt((org[i].x-org[j].x)*(org[i].x-org[j].x)+(org[i].y-org[j].y)*(org[i].y-org[j].y));
        scanf("%d",&m);
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            dis[a-1][b-1]=dis[b-1][a-1]=0;
        }
        if(!prim())puts("");
    }
}


目录
相关文章
|
机器学习/深度学习 人工智能 BI
codeforces-1242-B 0-1 MST
B. 0-1 MST time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Ujan has a lot of useless stuff in his drawers, a considerable part of which are his math notebooks: it is time to sort them out.
164 0
codeforces-1242-B 0-1 MST
|
算法 机器学习/深度学习
【POJ 1679 The Unique MST】最小生成树
无向连通图(无重边),判断最小生成树是否唯一,若唯一求边权和。 分析生成树的生成过程,只有一个圈内出现权值相同的边才会出现权值和相等但“异构”的生成树。(并不一定是最小生成树) 分析贪心策略求最小生成树的过程(贪心地选最短的边来扩充已加入生成树的顶点集合U),发现只有当出现“U中两个不同的点到V-U中同一点的距离同时为当前最短边”时,才会出现“异构”的最小生成树。
1239 0
|
人工智能 机器学习/深度学习 算法
【HDU 4463 Outlets】最小生成树(prim,kruscal都可)
以(x,y)坐标的形式给出n个点,修建若干条路使得所有点连通(其中有两个给出的特殊点必须相邻),求所有路的总长度的最小值。 因对所修的路的形状没有限制,所以可看成带权无向完全图,边权值为两点间距离。因是稠密图,故用邻接矩阵存储更好(完全图,边数e达到n(n-1)/2)。
1004 0
最短路径-zoj-2797
zoj-2797-106 miles to Chicago In the movie "Blues Brothers", the orphanage where Elwood and Jack were raised may be sold to the Board of Education if they do not pay 5000 dollars in taxes at the 
1191 0