hdu4009最小树形图-白红宇

hdu4009最小树形图

阅读量：4983 次

发布时间：2019-06-12

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

多建一个根，连到每一个点，然后花费是建水井的钱

然后跑一边最小树形图即可，这题必定有解，因为可以从根开始到每一点，可以不用判无解的情况

#include#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define pi acos(-1)#define ll long long#define mod 1000000007#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#define MIN(a,b) a
                   >n>>x>>y>>z){ if(n==0&&x==0&&y==0&&z==0)break; for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y>>p[i].z; int cnt=0; for(int i=1;i<=n;i++) { int k,s; cin>>k; while(k--){ cin>>s; e[cnt].u=i; e[cnt].v=s; e[cnt].w=dis(i,s)*y; if(p[s].z>p[i].z)e[cnt].w+=z; cnt++; } } for(int i=1;i<=n;i++) { e[cnt].u=0; e[cnt].v=i; e[cnt].w=x*p[i].z; cnt++; } dirmst(0,n+1,cnt)) cout<
                    
                     <