sinat_33185026 2016-03-29 03:29 采纳率: 0%
浏览 625

CCF 无线网络问题 求代码出现的问题

图片说明

 #include<iostream>
#include<cmath> 
#include<cstring>
#include<queue>

using namespace std;

int d[100][100];

struct plot
{
    long long x;
    long long y;
    int vis;
    long long dis;
}p[200];

int main()
{
    memset(d,0,sizeof(d));//d[]赋值全0 
    int m,n,k,num,t,f,knum,tt;
    long long r;

    //输入数据 
    cin>>n>>m>>k>>r;
    queue<int> q;
    for(int i=0;i<n+m;i++)
    {
     cin>>p[i].x>>p[i].y;
     p[i].vis=0;
     p[i].dis=pow(10,8)+1;
     } 


    //建立可达矩阵 
    for(int i=0;i<n+m;i++)
       for(int j=i+1;j<n+m;j++)
           {
            if((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)<=r*r)
            {
                d[i][j]=d[j][i]=1;
            }

           }


    //运用BFS 
    knum=0;
    num=0;
    q.push(0);
    p[0].dis=0;
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        p[t].vis=0;
        if(t>n)//如果被访问的结点是需要增设的,则需要的增设的数量+1 
        knum++;
        f=0;
        for(int i=1;i<n+m;i++)
           {
            if((d[t][i]==1)&&(p[i].vis==0))//如果该结点有可用邻接点而且该点是已存在的结点或者是需要增设的结点但是目前需要增设的数量小于上限 
            {
                if(i<=n||((i>n)&&(knum<k)))
                {

                    if(p[i].dis>p[t].dis+1)//如果原先从原点到该结点的距离大于通过t结点到达该结点的距离+1,则更改该结点的距离变量,并将其入队列 
                    {
                      q.push(i);
                       p[i].vis=1;
                      p[i].dis=p[t].dis+1;
                      f=1;

                    }

                }

            }


           }
        if(f==0&&t>n)//如果该结点没有可用的邻接点,而且是需要增设的,那么需要的增设的数量-1 
          knum--;

    }

    cout<<p[1].dis-1<<endl;//输出从源结点到目的结点的距离 


}
  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 delta降尺度计算的一些细节,有偿
    • ¥15 Arduino红外遥控代码有问题
    • ¥15 数值计算离散正交多项式
    • ¥30 数值计算均差系数编程
    • ¥15 redis-full-check比较 两个集群的数据出错
    • ¥15 Matlab编程问题
    • ¥15 训练的多模态特征融合模型准确度很低怎么办
    • ¥15 kylin启动报错log4j类冲突
    • ¥15 超声波模块测距控制点灯,灯的闪烁很不稳定,经过调试发现测的距离偏大
    • ¥15 import arcpy出现importing _arcgisscripting 找不到相关程序