UVALive - 5713 Qin Shi Huang's National Road System-白红宇

UVALive - 5713 Qin Shi Huang's National Road System

阅读量：5365 次

发布时间：2019-06-15

本文共 1701 字，大约阅读时间需要 5 分钟。

题意：

　　秦始皇要修路，n个城市，给出x,y坐标，和人口。

　　城市与城市之间的距离为它们的欧几里德距离。

　　徐福会魔法，他可以不费任何钱在两个城市中变出一条路出来。

　　问：

　　怎样才能使徐福变的那个路两边的城市人口之和最大，让秦始皇修的剩下的路花费的值最小，输出它们的比。

方法：

　　建图，求最小生成树，然后枚举每对城市u,v，始皇帝花的剩下的路的钱最小就是最小生成树的值减去最小生成树上的u,v之间路径上的最大权值。

然后比较枚举的每个边的情况的优劣即可。

代码：

#include
     
      using namespace std;#include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              int n,m;typedef long long LL;struct point{ LL x,y;};double countdist(const point&x,const point &y){ double ans1=0,ans2=0,ans=0; ans1=x.x-y.x; ans2=x.y-y.y; if (ans1<0) ans1*=-1;if (ans2<0) ans2*=-1; ans=sqrt((double)(ans1*ans1)+(double)(ans2*ans2)); return ans;}point a[3000];struct bian{ int l;int r;double d; bool operator<(const bian& pt)const{ return this->d
              
                tu[1100];double maxvalue[1100][1100];int v[1100];int dq;void dfs(int x,double dqmax){ maxvalue[dq][x]=dqmax; // cout<
               
                <<" "<
                
                 <<" "<
                 
                  <
                  
                   dqmax) ndq=tu[x][i].d; dfs(nb,ndq); }}void getmaxvalue(){ for (int i=1;i<=n;i++){ memset(v,0,sizeof(v)); dq=i; dfs(i,0); }}void deal(){ scanf("%d",&n); mapsnum=0; for (int i=0;i<=n;i++) tu[i].clear(); for (int i=1;i<=n;i++){ int dx,dy; scanf("%d%d",&dx,&dy); a[i].x=dx;a[i].y=dy; scanf("%lld",&people[i]); } for (int i=2;i<=n;i++){ for (int j=1;j
                   
                    =n-1) break; k++; } // cout<<"maxscs: "<
                    
                     <<"\t"<<"maxk: "<
                     
                      <<"\tmaxnum: "<
                      
                       <
                       
                        =0;i--){ LL rq=people[maps[i].l]+people[maps[i].r]; double dd=maxvalue[maps[i].l][maps[i].r]; double zans; double nd=scsans-dd; zans=(double)rq/nd; //cout<
                        
                         <<" "<
                         
                          <
                          
                           ans) ans=zans; } printf("%.2f\n",ans);}int main(){ int t; scanf("%d",&t); while(t--){ deal(); } return 0;}

转载于:https://www.cnblogs.com/xfww/p/7628035.html

你可能感兴趣的文章