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("");
    }
}


目录
相关文章
|
6月前
poj 3298 数状数组
题目大意是一条大街上住着n个乒乓球爱好者,他们的水平高低用一个数值表示,他们经常举办比赛,比赛要三个人,一人当裁判。对裁判是有一定要求的,裁判的水平必须介于两选手之间且必须住他们中间,计算可以举办多少场比赛
23 0
POJ 1936 All in All
POJ 1936 All in All
63 0
|
算法 数据建模 机器学习/深度学习
|
人工智能 BI
poj-3185-开关问题
描述   牛一行20他们喝的水碗。碗可以那么(面向正确的为清凉水)或颠倒的(一个位置而没有水)。他们希望所有20个水碗那么,因此用宽鼻子翻碗。   嘴太宽,他们不仅翻转一碗还碗的碗两侧(总共三个或三个——在两端的情况下碗——两碗)。
784 0
|
消息中间件 人工智能 JavaScript