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条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥60 版本过低apk如何修改可以兼容新的安卓系统
    • ¥25 由IPR导致的DRIVER_POWER_STATE_FAILURE蓝屏
    • ¥50 有数据,怎么建立模型求影响全要素生产率的因素
    • ¥50 有数据,怎么用matlab求全要素生产率
    • ¥15 TI的insta-spin例程
    • ¥15 完成下列问题完成下列问题
    • ¥15 C#算法问题, 不知道怎么处理这个数据的转换
    • ¥15 YoloV5 第三方库的版本对照问题
    • ¥15 请完成下列相关问题!
    • ¥15 drone 推送镜像时候 purge: true 推送完毕后没有删除对应的镜像,手动拷贝到服务器执行结果正确在样才能让指令自动执行成功删除对应镜像,如何解决?