PAT-1018 Public Bike Management (30)

港控/mmm° 2021-11-22 04:56 178阅读 0赞

直接用dijkstra求取，只能拿到22,四个case过不了

#include<stdio.h>
    #include<stack>
    using namespace std;
    
    int bike_count[510];
    int bike_sum[510]; 
    int bike_sum_num[510];
    int map[510][510];
    bool visited[510];
    int d[510];
    int pre[510];
    int Max=0xffffffff>>1;
    //max=max>>1;
    
    int findMin(int n)
    {
        int min=Max,index=-1;
        for(int i=0;i<=n;i++)
        {
          if(!visited[i]&&d[i]<min)
          {
              min=d[i];
              index=i;
          }
        }
        return index;
    } 
    
    
    int main()
    {
         int maxc,n,sp,m;
         int a,b,val;
         freopen("1018-in.txt","r",stdin);
         freopen("1018-out.txt","w",stdout);
         while(scanf("%d%d%d%d",&maxc,&n,&sp,&m)!=EOF)
         {
           for(int i=0;i<=n;i++)//init map 
            {
              for(int j=0;j<=n;j++)
              {
                 map[i][j]=Max;
              }
              visited[i]=false;
              d[i]=Max;
              bike_sum[i]=0;
              bike_sum_num[i]=0;
              pre[i]=0;
            }
            bike_count[0]=0;
            for(int i=1;i<=n;i++)
            {
              scanf("%d",&bike_count[i]);
            }
            
            for(int i=0;i<m;i++)
            {
              scanf("%d%d%d",&a,&b,&val);
              map[a][b]=map[b][a]=val;
            }
            
            //begin dijkstra
            int index;
            d[0]=0;
            pre[0]=-1;
             while(true)
             {
                index=findMin(n);
                //for(int s=0;s<n;s++)
                 // printf("%d ",d[s]); 
                //("\n");
                visited[index]=true;
                //printf("index=%d\n",index);
                if(index==-1)
                  break;
                for(int i=0;i<=n;i++)
                {
                  if(map[i][index]!=Max&&d[i]>d[index]+map[index][i])
                  {
                     d[i]=d[index]+map[index][i];
                     bike_sum[i]=bike_sum[index]+bike_count[i];
                     bike_sum_num[i]=bike_sum_num[index]+1;
                     pre[i]=index;
                     //printf( "0 i=%d,index=%d %d\n",i,index,bike_sum[i]);
                  }
                  else if(map[i][index]!=Max&&d[i]==d[index]+map[index][i])
                  {
                     double a=(bike_sum[i]/(bike_sum_num[i]*1.0));
                     double b=(bike_sum[index]+bike_count[i])/((bike_sum_num[index]+1)*1.0);
                     //printf("%lf %lf\n",a,b);
                     if(a>maxc/2.0&&b>=maxc/2.0&&a>b)
                     {
                          d[i]=d[index]+map[index][i];
                          bike_sum[i]=bike_sum[index]+bike_count[i];
                          bike_sum_num[i]=bike_sum_num[index]+1;
                          pre[i]=index;
                          //printf("1 i=%d,index=%d,%d\n",i,index,bike_sum[i]);
                     }
                     if(a<maxc/2.0&&b<=maxc/2.0&&a<b)
                     {
                          d[i]=d[index]+map[index][i];
                          bike_sum[i]=bike_sum[index]+bike_count[i];
                          bike_sum_num[i]=bike_sum_num[index]+1;
                          pre[i]=index;
                          //printf("2 i=%d,index=%d,%d\n",i,index,bike_sum[i]);
                     } 
                     if(a<maxc/2.0&&b>=maxc/2.0)
                     {
                          d[i]=d[index]+map[index][i];
                          bike_sum[i]=bike_sum[index]+bike_count[i];
                          bike_sum_num[i]=bike_sum_num[index]+1;
                          pre[i]=index;
                          //printf("3 i=%d,index=%d,%d\n",i,index,bike_sum[i]);
                     }
                     /*if(b==maxc/2.0)
                     {
                          d[i]=d[index]+map[index][i];
                          bike_sum[i]=bike_sum[index]+bike_count[i];
                          bike_sum_num[i]=bike_sum_num[index]+1;
                          pre[i]=index;
                     }*/
                     //printf("4 i=%d,index=%d,%d\n",i,index,bike_sum[i]);
                  }
                }
             }//while(true)
             //printf("%d\n",bike_sum[sp]); 
             //printf("%d\n",bike_sum_num[sp]); 
              int mod=bike_sum_num[sp]*maxc/2-bike_sum[sp];
              printf("%d ",mod>=0?mod:0);
              int p=sp;
              stack<int> path;
              path.push(sp);
              while(true)
              {
                 p=pre[p];
                 if(p==-1)
                   break;
                 path.push(p);
              }
              while(!path.empty())
              {
                  printf("%d",path.top());
                  if(path.size()!=1)
                   printf("->");
                  path.pop();
              }    
              printf(" %d\n",mod<=0?0-mod:0);
         }
        return 0;
    }

网上找了一下，发现一个坑，那就是后面的站点的车辆不能运送会前面的站点，所以会还有四个测试数据没有通过，需要DIJSKSTRA+DFS来实现。需要保存所有的路径下来。

后续再补上。

==================

这次试用dijkstra+dfs算法实现。可以拿到29分，据说测试数据9是大数据，用现在方法写出的程序，时间复杂读比较大，dfs之后，还需要扫描所有出来的路径，这一步，本来可以在dfs的时候就完成的，但是由于回朔工地太差了，没有继续做下去。

// 1018a.cpp : 定义控制台应用程序的入口点。
    //
    #include "StdAfx.h"
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<iostream>
    #include<vector>
    using namespace std;
    
    #define MAX 1010
    int d[MAX];
    int bike_count[MAX];
    int map[MAX][MAX];
    int maxInt=0xffffffff>>1;
    bool visited[MAX];
    bool vis[MAX];
    
    int findMinIndex(int n)
    {
        int min=maxInt,minIndex=-1;
        for(int i=0;i<=n;i++)
        {
          if(!visited[i]&&min>d[i])
          {
             min=d[i];
             minIndex=i;
          }
        }
        return minIndex;
    }
    
    struct Path
    {
      vector<int> v;
      int bike_need;
      int before;
      int count;
    };
    Path p;
    vector<Path> path;
    int cmax,n,sp,m;
    int a,b,tmp;
    
    vector<int>::iterator it;
    void dfs(int node,int dist,int n,int max_dist)
    {
        //cout<<node<<" "<<dist<<" "<<n<<" "<<max_dist<<endl;
        vis[node]=true;
        if(dist>max_dist)
           return;
         p.v.push_back(node);
         p.count++;
        if(dist==max_dist)//lost node==sp
        {
          vector<int>::iterator it=p.v.begin();
          for(;it!=p.v.end();it++)
           {
              cout<<*it<<" ";
           }
           cout<<endl;
           if(node==sp)
              path.push_back(p);
           //p.v.clear()
         it=p.v.begin();
         for(;it!=p.v.end();it++)
         {
              if(*it==node)
              {
                  p.v.erase(it);
                  p.count--;
                 cout<<"delete q"<<node<<endl;
                  break;
              }
         }
           vis[node]=false;
           return;
        }
    
        for(int i=0;i<=n;i++)
        {  
          if(map[i][node]!=maxInt&&!vis[i])
          {
              //cout<<i<<" "<<endl;
              dist=dist+map[i][node];//
              dfs(i,dist,n,max_dist); 
              dist=dist-map[i][node];//
          } 
        }
         vis[node]=false;
         it=p.v.begin();
         for(;it!=p.v.end();it++)
         {
              if(*it==node)
              {
                p.v.erase(it);
                p.count--;
                cout<<"delete"<<node<<endl;
                break;//attention
              }
         }
    }
    
    void dfsg(int n,int max_dist)
    {
         /*for(int i=0;i<=n;i++)
         {
            if(!vis[i])
               dfs(i,0,n,max_dist);
         }*/
         dfs(0,0,n,max_dist); 
    }
    
    
    int main()
    {
       freopen("1018-in.txt","r",stdin);
       freopen("1018-out.txt","w",stdout);
       p.bike_need=0;
       p.count=0;
       p.before=0;
        while(cin>>cmax>>n>>sp>>m)
        {
           memset(map,0,sizeof(int)*MAX*MAX);
           d[0]=0;
           map[0][0]=0;
          /* for(int i=1;i<=n;i++)
           {
             cin>>bike_count[i];
             d[i]=maxInt;
             visited[i]=false;
             map[i][i]=maxInt;
             vis[i]=false;
           }*/
           for(int i=0;i<=n;i++)//map初始化为无穷maxInt 
           {
             for(int j=0;j<=n;j++)
             {
                map[i][j]=maxInt;
             } 
             if(i!=0)
             {
                 cin>>bike_count[i];
                 d[i]=maxInt;
                 visited[i]=false;
                 map[i][i]=maxInt;
                 vis[i]=false;
             }
           }
           for(int j=0;j<m;j++)
           {
              cin>>a>>b>>tmp;
              map[a][b]=map[b][a]=tmp;
           }
           int index;
           while(true)
           {
              index=findMinIndex(n);
             // cout<<index<<endl;
              if(index==-1)
                  break;
              for(int i=1;i<=n;i++)
              {
                 if(!visited[index]&&map[index][i]!=maxInt)//是否需要visited 
                 {
                     if(d[i]>d[index]+map[index][i])
                        d[i]=d[index]+map[index][i];
                 }
              }
              visited[index]=true;       
           }
           
           cout<<d[sp]<<endl;
           
    
           dfsg(n,d[sp]);  
           bike_count[0]=cmax/2;
           vector<Path>::iterator it=path.begin();
           int result=-1;
           int result_need=0;
           int result_before=0;
           for(int s=0;s<path.size();s++)
           {
               Path p=*(it+s);
               int bike_need=0;
               int bike_before=0;
    
               for(int j=0;j<p.v.size();j++)
               {
                   int node=p.v[j];
                   if(bike_count[node]>=cmax/2)
                       bike_before+=(bike_count[node]-cmax/2);
                   else
                   {
                       if(bike_before+bike_count[node]>=cmax/2)
                       {
                           int temp=(bike_before+bike_count[node]-cmax/2);
                           bike_before=temp;           
                       }
                       else
                       {
                           bike_need+=(cmax/2-bike_before-bike_count[node]);
                           bike_before=0;
                       }
                   }
               }
               if(result==-1)
                {
                    result=s;
                    result_need=bike_need;
                    result_before=bike_before;
               }
               else
               {
                   if(result_need>bike_need)
                   {
                        result=s;
                        result_need=bike_need;
                        result_before=bike_before;
                   }
                   else if(result_need==bike_need)
                   {
                       if(result_before>bike_before)
                       {
                               result=s;
                            result_need=bike_need;
                            result_before=bike_before;
                       }
                   }
               }
           }
           //测试数据9,是大数据测试点，过不了
          cout<<result_need<<" ";
          p=path[result];
          for(int i=0;i<p.v.size();i++)
          {
              cout<<p.v[i];
              if(i!=p.v.size()-1)
                  cout<<"->";
          }
          cout<<" "<<result_before<<endl;
        }
    }

转载于:https://www.cnblogs.com/championlai/p/3990895.html