cafelier@SRM

SRM491 900

あとで | 14:38 |

• この最小費用流、おそいぞ…

template<typename T>
class IdGen
{
   map<T, int> v2id_;
   vector<T>   id2v_;
public:
   int v2id(const T& v)
   {
      if( !v2id_.count(v) )
      {
         v2id_[v] = size();
         id2v_.push_back(v);
      }
      return v2id_[v];
   }
   const T& id2v(int i) const { return id2v_[i]; }
   int size() const { return id2v_.size(); }
};

template<typename Vert, typename Cost, typename Flow, int NV=256>
class MinCostFlow
{
   IdGen<Vert> idgen;

   vector<int> G[NV];
   Flow F[NV][NV];
   Cost C[NV][NV];

public:
   void addEdge( Vert s_, Vert t_, Cost c, Flow f )
   {
      int s = idgen.v2id(s_), t = idgen.v2id(t_);
      G[s].push_back(t);
      G[t].push_back(s);
      C[s][t] = c;
      C[t][s] = -c;
      F[s][t] = f;
      F[t][s] = 0;
   }

   pair<Cost, Flow> calc( Vert s_, Vert t_ )
   {
      const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_);
      static const Cost COST_INF = 1e+300; // !!EDIT HERE!!
      static const Flow FLOW_INF = 0x7fffffff;


      Cost total_cost = 0;
      Flow total_flow = 0;
      vector<Cost> h(N, 0); // potential
      for(Flow RF=FLOW_INF; RF>0; ) // residual flow
      {
         // Dijkstra -- find the min-cost path
         vector<Cost> d(N, COST_INF);  d[S] = 0;
         vector<int>  prev(N, -1);

         typedef pair< Cost, pair<int,int> > cedge;
         priority_queue< cedge, vector<cedge>, greater<cedge> > Q;
         Q.push( cedge(0, make_pair(S,S)) );
         while( !Q.empty() ) {
            cedge e = Q.top(); Q.pop();
            if( prev[e.second.second] >= 0 )
               continue;
            prev[e.second.second] = e.second.first;

            int u = e.second.second;
            for(int i=0; i<G[u].size(); ++i) {
               int  v = G[u][i];
               Cost r_cost = C[u][v] + h[u] - h[v];
               if( F[u][v] > 0 && d[v] > d[u]+r_cost )
                  Q.push( cedge(d[v]=d[u]+r_cost, make_pair(u,v)) );
            }
         }

         if( prev[T] < 0 )
            break; // Finished

         // As much as possible
         Flow f = RF;
         for(int u=T; u!=S; u=prev[u])
            f = min(f, F[prev[u]][u]);
         RF         -= f;
         total_flow += f;

         for(int u=T; u!=S; u=prev[u])
         {
            total_cost    += f * C[prev[u]][u];
            F[prev[u]][u] -= f;
            F[u][prev[u]] += f;
         }

         // Update the potential
         for(int u=0; u<N; ++u)
            h[u] += d[u];
      }
      return make_pair(total_cost, total_flow);
   }
};

class FoxCardGame { public:
   double theMaxProportion(vector <double> pileA, vector <double> pileB, int k) 
   {
      double L=1, R=50;
      for(int i=0; i<50; ++i)
         (possible(pileA, pileB, k, (L+R)/2) ? L : R) = (L+R)/2;
      return L;
   }

   enum Tag {Src, Left, Right, Target, Goal};
   bool possible(vector <double> pileA, vector <double> pileB, int k, double R)
   {
      MinCostFlow<pair<Tag,int>, double, int> mcf;

      for(int a=0; a<pileA.size(); ++a)
         mcf.addEdge( make_pair(Src,0), make_pair(Left,a), 0.0, 1 );
      for(int a=0; a<pileA.size(); ++a)
      for(int b=0; b<pileB.size(); ++b)
      {
         double x_ = pileA[a]+pileB[b], y_ = pileA[a]*pileB[b];
         double x = max(x_,y_), y = min(x_,y_);
         mcf.addEdge( make_pair(Left,a), make_pair(Right,b), R*y-x+10000.0, 1 );
      }
      for(int b=0; b<pileB.size(); ++b)
         mcf.addEdge( make_pair(Right,b), make_pair(Target,0), 0.0, 1 );
      mcf.addEdge( make_pair(Target,0), make_pair(Goal, 0), 0.0, k );

      return mcf.calc( make_pair(Src,0), make_pair(Goal,0) ).first <= 10000.0*k;
   }
};

• 「二分探索で Σx / Σy ≧ R にできる R の最大値を探す」
• 式変形すると「Σ(Ry-x) ≦ 0 にできる R の最大値を探す」
• つまり「Σ(Ry-x) を最小にする」
• 「最小費用流」

• それはいいんだけど、2secギリギリ近くかかる。
• 最小費用流の改良しておいた方がいいかなあ。