poj1639 Picnic Planning 最小度数限制生成树 - c++编程基础

TOP

poj1639 Picnic Planning 最小度数限制生成树

2015-07-20 18:04:43 来源: 作者: 【大中小】浏览:2次

题意：若干个人开车要去park聚会，但是park能停的车是有限的，为k。所以这些人要通过先开车到其他人家中，停车，然后拼车去聚会。另外，车的容量是无限的，他们家停车位也是无限的。求开车总行程最短。
就是求一最小生成树，但是对于其中一个点其度不能超过k。

思路：

1. 将park点取出将剩下的点求出最小生成树出现i个联通块

2. 再每个块中选择与park点相邻的最小边

到此park点已经连了i条边

park点最大可以连接k个点

得到Sum值

3. 需要求出i+1-->k 条的Sum值

每次添加一条边在树上形成一个环然后删去一条环上的边（权值最大）取Sum=min（Sum，Sum+添加边-删去边）复杂度O(n^2)

因为第三步复杂度高需要优化第三步

优化：先记录Vi->Vp路径上且不与Vp直接相连的边的权值的Max[ i ]

添加边时取cost(Vi,Vp)-Max [ i ]最小值添加(Vi,Vp)边

再枚举ViVp原有的路径上不与Vp相连的边，找到最大权值的边；

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               using namespace std; const int maxn =111+5; const int maxe = 15000+5; const int INF = 460002326; #include 
               map
               
                mp; map
                
                 ::iterator it; int car,n,cost[maxn][maxn],sum,father[maxn]; int best[maxn]; bool vis[maxn]; bool edge[maxn][maxn]; bool use[maxn]; void dfs(int root)//将一个连通块中各个点标记其father { for(int i=1; i
                 
                  dis[i])) { Min_i=i; Min=dis[i]; } } if(Min==INF) break; sum+=Min; vis[Min_i]=true; use[Min_i]=true;//标记连通块用过的点 edge[Min_i][num[Min_i]]=edge[num[Min_i]][Min_i]=true; for(int i=0; i
                  
                   cost[i][Min_i]) { num[i]=Min_i; dis[i]=cost[i][Min_i]; } } } Min=INF; int root=-1; for(int i=0; i
                   
                    cost[father[j]][j]) best[j]=tmp; else best[j]=j; } else best[j]=j;//其父节点与source相连 将j赋给自己 return best[j]; } void solve() { int mst=0; memset(father,-1,sizeof(father)); memset(use,0,sizeof(use)); memset(edge,false,sizeof(edge)); use[0]=true; for(int i=0; i
                    
                     cost[0][j]-cost[ax][bx])//cost[0][j]表示添加的边 cost[ax][bx]表示断开的边 { minadd=cost[0][j]-cost[ax][bx];//更新减小的值以及连接的点 change=j; } } } if(minadd>=0) //表示要增加sum值 则已经得到最小的sum值 break; sum+=minadd;//更新 ax=best[change]; bx=father[ax]; cost[ax][bx]=cost[bx][ax]=INF; father[change]=0; cost[0][change]=cost[change][0]=INF; } } int main() { int t; // freopen("in.txt","r",stdin); cin>>t; mp.clear(); string s1,s2; int val; for(int i=0; i
                     
                      >s1>>s2>>val; it=mp.find(s1);//map映射值 if(it==mp.end()) mp[s1]=n++; it=mp.find(s2); if(it==mp.end()) mp[s2]=n++; if(cost[mp[s1]][mp[s2]]>val)//可能会有重边。事实上没有。。。。。 cost[mp[s1]][mp[s2]]=cost[mp[s2]][mp[s1]]=val; } cin>>car; solve(); cout<<"Total miles driven: "<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C++中面向对象的理解	下一篇：HDU 4864 Task(贪心)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: