并查集的另类思想应用

- 日理万妓 2024-01-08 07:41 7阅读 0赞

#define MAX_PACK 10
    #include <stdint.h>
    #include <vector>
    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<string>
    #include<map>
    #include<set>
    #include<sys/time.h>
    #include<stdlib.h>
    #include<iterator>
    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/1000;
    }  
    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 outputvec(vector<vector<int> >num)
    {
       if(num.size()>0)
       {
           cout << "num cnt =" << num.size() << endl;
       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;
       }
    }
    //容器vector中元素的去重
    void uvector(vector<int>&v){
    	vector<int>::iterator vector_iterator;
    	sort(v.begin(),v.end());
    	vector_iterator = unique(v.begin(),v.end());
    	if(vector_iterator != v.end()){
    		v.erase(vector_iterator,v.end());
    	}
    }
    
    
    //基于司机将订单分组
    void getod(vector<TripFeature>&  trip_list,vector<vector<int> >&ordervec)
    {
        set<int>driver;
        for(int i=0;i<trip_list.size();i++)
        {
            driver.insert(trip_list[i].driver_id);
        }
        set<int>::iterator it;              
        for(it=driver.begin();it!=driver.end();it++)  //使用迭代器进行遍历   
        {   vector<int>order;
            for(int i=0;i<trip_list.size();i++)
            {
                 if(*it==trip_list[i].driver_id)
                 {
                     for(int j=0;j<trip_list[i].order_list.size();j++)
                     {
                           order.push_back(trip_list[i].order_list[j]);
                     }
                 }
            }  
           uvector(order);
           ordervec.push_back(order);
        }  
    }
    
    void unionserch(vector<vector<int> >&v,vector<vector<int> >&orderset)//遍历集合，建立映射
    {
         int idex=0;
         int group=1;
         map<int,int>mp;//索引之间的映射（现有集合索引，当前数组坐标索引）
         mp[idex]=group;//行号v的下标索引，集合编号,
        
         //vector<int>::iterator k = v.begin();
         //v.erase(k);//建立完关系从数组中删除
         for(int i=1;i<v.size();i++)//从下一个订单集合开始对比 v[1]的元素在v0中是否存在
         {
           
            for(int j=0;j<mp.size();j++)//查找mp中所映射的订单集合中是否和当前集合中元素有交集
            {
                vector<int>tmp;
                int videx=getmapfirst(mp,mp[j]);
                set_intersection(v[videx].begin(),v[videx].end(),v[i].begin(),v[i].end(),back_inserter(tmp));
                if(!tmp.empty())//如果有交集，则把其合并
                {
                   if(!mp[i])
                   {
                   vector<int>mergev;
                   set_union(v[videx].begin(),v[videx].end(),v[i].begin(),v[i].end(),back_inserter(mergev));
                   v[videx].assign(mergev.begin(),mergev.end());
                   mp[i]=mp[j];//第一次赋值
                   }
                   else{
                         int videx=getmapfirst(mp,mp[i]);//第二次看订单所在的组的组号的数组坐标，把当前组合入
                         int jdex=getmapfirst(mp,mp[j]);
                         vector<int>mergev;
                         set_union(v[videx].begin(),v[videx].end(),v[jdex].begin(),v[jdex].end(),back_inserter(mergev));
                         v[videx].assign(mergev.begin(),mergev.end());
                         mp[j]=mp[i];
                          
                       }
                }
                else {
                    group++;
                    mp[i]=group;
                }
                
            }
         }
         set<int>groupset;
         set<int>::iterator setit;
         map<int,int>::iterator mpit;
         for(mpit=mp.begin();mpit!=mp.end();mpit++)
         {
             groupset.insert(mpit->second);
         }
         for(setit=groupset.begin();setit!=groupset.end();setit++)
         {
            int vindex=getmapfirst(mp,*setit);
            orderset.push_back(v[vindex]);
         }
        
    }
    
    void SplitTripList(vector<TripFeature>&  trip_list,vector<vector<int> >&  split_trip_list,vector<vector<int> >&orderset) {
             
             for(int i=0;i<orderset.size();i++)
             {
               vector<int>trip;
               for(int j=0;j<trip_list.size();j++)
               {
                    vector<int>::iterator iter=std::find(orderset[i].begin(),orderset[i].end(),trip_list[j].order_list[0]);//返回的是一个迭代器指针
                    if(iter!=orderset[i].end())
                    {
                        trip.push_back(trip_list[j].trip_id);
                    }
               }
               split_trip_list.push_back(trip);
             }
    }
    void loaddate(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);
        }
    }
    void load(vector<TripFeature>& trip_list)
    {
        TripFeature trip1;
        trip1.driver_id=1;
        trip1.trip_id=1;
        for(int i=1;i<4;i++)
        {
            trip1.order_list.push_back(i);
        }
        trip1.order_list.push_back(20);
        trip_list.push_back(trip1);
    
        TripFeature trip2;
        trip2.driver_id=2;
        trip2.trip_id=2;
        for(int i=2;i<6;i++)
        {
            trip2.order_list.push_back(i);
        }
        trip_list.push_back(trip2);
    
        TripFeature trip3;
        trip3.driver_id=3;
        trip3.trip_id=3;
        for(int i=7;i<9;i++)
        {
            trip3.order_list.push_back(i);
        }
        trip_list.push_back(trip3);
    
       
        TripFeature trip4;
        trip4.driver_id=4;
        trip4.trip_id=4;
        for(int i=5;i<9;i++)
        {
            trip4.order_list.push_back(i);
        }
        trip_list.push_back(trip4);
    
        TripFeature trip5;
        trip5.driver_id=5;
        trip5.trip_id=5;
        for(int i=9;i<13;i++)
        {
            trip5.order_list.push_back(i);
        }
        trip_list.push_back(trip5);
    
        TripFeature trip6;
        trip6.driver_id=1;
        trip6.trip_id=6;
        for(int i=3;i<7;i++)
        {
            trip6.order_list.push_back(i);
        }
        trip_list.push_back(trip6);
        TripFeature trip7;
    
        trip7.driver_id=7;
        trip7.trip_id=7;
        for(int i=99;i<101;i++)
        {
            trip7.order_list.push_back(i);
        }
    
        trip_list.push_back(trip7);
    }
    int main(int argc, char** argv){
        static double t0,t1,t2,t3,t4,t5;
        vector<TripFeature>trip_list;
        vector<vector<int> >od;
        vector<vector<int> >orderset;
        vector<vector<int> >split_trip_list;
      loaddate(trip_list);
    //    load(trip_list);
        
        t0=get_wall_time();
        getod(trip_list,od);
        t1=get_wall_time();
       // outputvec(od);
        t2=get_wall_time();
        unionserch(od,orderset);
        t3=get_wall_time();
       // outputvec(orderset);
        t4=get_wall_time();
        SplitTripList(trip_list,split_trip_list,orderset);
        t5=get_wall_time();
      //  outputvec(split_trip_list);
       // cout<<"getodcost="<<t1-t0<<"    "<<"unionserchcost="<<t3-t2<<"   "<<"splittripcost="<<t5-t4<<endl;
        cout<<"totalcost="<<t5-t0<<"ms"<<endl;
        return 0;
    }