基于最强连通分量的应用

╰+哭是因爲堅強的太久メ 2024-01-08 07:41 44阅读 0赞

#define MAX_PACK 10
    #include <stdint.h>
    #include <vector>
    #include<iostream>
    #include<algorithm>
    #include<string>
    #include<map>
    #include<set>
    #include<sys/time.h>
    #include<stdlib.h>
    using namespace std;
    bool rel[1000][1000];
    
    int rad[4][2]={
       {1,0},{0,1},{-1,0},{0,-1}};
    struct TripFeature {
        vector<int>order_list;
        int trip_id;
        int driver_id;
    };
    double get_wall_time()    
    { 
            struct timeval time ;  
            if (gettimeofday(&time,NULL)){          
                     return 0;  
            }  
        return (double)time.tv_sec*1000 + (double)time.tv_usec*0.001;                
    }  
    int check(int x,int y,int n){//判断搜索到的位置是否合理
            return x>=0 && y>=0 && x<n && y<n;
    }
    
    void getorder(vector<TripFeature>&  trip_list,vector<int>&ordervec)
    {
         set<int>orderset;
         for(int i=0;i<trip_list.size();i++)
         {
             for(int j=0;j<trip_list[i].order_list.size();j++)
                 
                {
                    orderset.insert(trip_list[i].order_list[j]);
                }
         }
        
        ordervec.assign(orderset.begin(), orderset.end());
    }
    
    void outputvec(vector<vector<int> >num)
    {
       if(num.size()>0)
       {
        
       for(int i=0;i<num.size();i++)
       {
           for(int j=0;j<num[i].size();j++)
           {
               cout<<num[i][j]<<" ";
           }
           cout<<endl;
       }
       }
       else
       {
           cout<<"数组空"<<endl;
       }
    }
    void orderhash(vector<int>ordervec,map<int,int>&ordermap)
    {
        for(int i=0;i<ordervec.size();i++)
        {
            ordermap[i]=ordervec[i];
        }
    
    }
    
    
    int getmapfirst(map<int,int>&mp,int val)
    {
         map<int, int>::iterator it;
        for (it = mp.begin(); it != mp.end(); it++)
         {   
             if(it->second==val)
                 return it->first;
         }
    }
    void relation(vector<TripFeature>&  trip_list,map<int,int>ordermap)
    {
       for(int i=0;i<trip_list.size();i++)
       {   vector<int>ordervec;
           
           for(int j=0;j<trip_list[i].order_list.size();j++)
           {
              ordervec.push_back(trip_list[i].order_list[j]);
              for(int k=0;k<trip_list.size();k++)
              {
                  if(trip_list[k].driver_id==trip_list[i].driver_id)
                  {
                      ordervec.push_back(trip_list[k].order_list[j]);
                  }
              }
           }
        
           for(int m=0;m<ordervec.size();m++)
           {
              int first1=getmapfirst(ordermap,ordervec[m]);
              for(int n=0;n<ordervec.size();n++)
              {
                int first2=getmapfirst(ordermap,ordervec[n]);
                rel[first1][first2]=true;
                rel[first2][first1]=true;
              }
           }
       }
    }
    void dfs(set<int>&orderset,int x,int y,int size)
    {
        rel[x][y]=false;
        for(int i=0;i<4;i++)
        {
           int xx=x+rad[i][0];
           int yy=y+rad[i][1];
           if(check(xx,yy,size) && rel[xx][yy])
           {
            int n=max(xx,yy);
            orderset.insert(n);
            dfs(orderset,xx,yy,size);
           }  
        }
    }
    void find(vector<TripFeature> trip_list,int orderid,vector<int>&tripn)
    {
        
        for(int i=0;i<trip_list.size();i++)
        {
            vector<int>::iterator iter=std::find(trip_list[i].order_list.begin(),trip_list[i].order_list.end(),orderid);//返回的是一个迭代器指针
                    if(iter!=trip_list[i].order_list.end())
                    {
                        tripn.push_back(trip_list[i].trip_id);
                    }
        }
        
    
    }
    void SplitTripList(vector<TripFeature>&  trip_list,   vector<vector<int> >&  split_trip_list) {
             vector<int>ordervec;
             map<int,int>ordermap;
             vector<vector<int> >ordersetvec;
             getorder(trip_list,ordervec);
             int size=ordervec.size();
             orderhash(ordervec,ordermap);
             relation(trip_list,ordermap);
             int pn=0; 
                 
             for(int i=pn;i<size;i++)
             {  
               /* 
                 cout<<i<<endl;
                 for(int m=0;m<size;m++)
                 {
                     for(int n=0;n<size;n++)
                     {
                         cout<<rel[m][n]<<" ";
                     }
                     cout<<endl;
                 }*/
                 vector<int>ovec;
                 set<int>orderset;
                 for(int j=pn;j<size;j++)
                 {
                     if(rel[i][j])
                     {
                     orderset.insert(i);
                     orderset.insert(j);
                     dfs(orderset,i,j,size);
                     }
                 }
                    
                 int n=orderset.size();
                 for(int i=pn;i<pn+n;i++)
                 {
                     for(int j=pn;j<pn+n;j++)
                     {
                         rel[i][j]=false;
                     }
               
                }
                 pn+=n;
    
                 
                 ovec.assign(orderset.begin(),orderset.end());
                 if(ovec.empty())
                 {
                     continue;
                 }
                 ordersetvec.push_back(ovec);
             }
             
            // cout<<"ordersetsize:"<<ordersetvec.size()<<endl;
    //   outputvec(ordersetvec);
             for(int i=0;i<ordersetvec.size();i++)
             {
                 vector<int>trip;
                 set<int>tripset;
                 for(int j=0;j<ordersetvec[i].size();j++)
                 {
                      vector<int>rn;
                      find(trip_list,ordermap[ordersetvec[i][j]],rn);
                     if(rn.size()>0)
                     {
                        for(int i=0;i<rn.size();i++)
                        {
                         tripset.insert(rn[i]);
                        }
                     }
                 }
              trip.assign(tripset.begin(),tripset.end());
              split_trip_list.push_back(trip);
             }
                 
    }
    void loaddate(const char* path,vector<TripFeature>&  trip_list)
    {
        for(int i=0;i<3000;i++)
        {
           srand((unsigned)time(NULL));
           TripFeature trip;
           trip.driver_id=rand() % 100 + 1;
           trip.trip_id=i+1;
           int n=rand()%5+1;
           for(int i=0;i<n;i++)
           {
                 int orderid=rand()%500+1;
                 trip.order_list.push_back(orderid);
           }
            trip_list.push_back(trip);
        }
    }
    
    int main(int argc, char** argv){
    
        float newtotal_cost;
        int n=10000;
        vector<TripFeature>trip_list;
        vector<vector<int> >split_trip_list;
        loaddate("", trip_list);
        
        double t1 = get_wall_time(); 
        SplitTripList(trip_list,split_trip_list);
       // outputvec(split_trip_list);
        double t2 = get_wall_time(); 
        cout<<"cost:" << t2-t1<<"ms"<<endl;
    
        return 0;
    }