cafelier@SRM

SRM468 1000

あとで | 12:33 |

上に書いた方針で。結構長くなってしまった。

typedef int           vert;
typedef vert          edge;
typedef vector<edge>  edges;
typedef vector<edges> graph;

bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] )
{
   for(int i=0; i<G[v].size(); ++i) {
      vert u = G[v][i];
      if( visited[u] ) continue;
      visited[u] = true;

      if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) )
         { matchTo[v]=u, matchTo[u]=v; return true; }
   }
   return false;
}

template<int NV>
int biMatch( graph& G, int L ) // [0,L):left, [L,?):right
{
   vector<vert> matchTo(G.size(), -1);
   int ans = 0;
   for(vert v=0; v<L; ++v) {
      bool visited[NV] = {};
      if( augment(G, v, matchTo, visited) )
         ++ans;
   }
   return ans;
}

int bitcnt(LL x)
{
   int c = 0;
   for(; x; x>>=1)
      c += x&1;
   return c;
}

class MallSecurity { public:
   pair<graph, int> generateBipartiteGraph(
      const vector<int>& As, const vector<int>& Bs, const vector<int>& Cs, const vector<int>& Ds,
      const vector<int>& Ks, int msf, int mask )
   {
      // construct a bipartite graph representation, in which
      //   - "even"-floor stations go to the left
      //   - "odd"-floor stations go to the right
      // here floor number is normalized by rotating the msf-th floor to zero
      #define LR(f) (((f)>msf ? (f)-msf : Ks.size()-msf+(f))%2)

      // assign interger-ID for each "choosable" station, i.e.,
      // a station which is not at msf and is not connected to a 'mask'ed station on msf
      map<pair<int,int>,int> ID;
      int nextID[2] = {0,0}; // use different sets of IDs for even/odd floors
      {
         for(int f=0; f<Ks.size(); ++f) if( f != msf )
         for(int i=0; i<Ks[f]; ++i)
         {
            bool can_use = true;
            for(int j=0; j<As.size(); ++j)
               if( Cs[j]==f && As[j]==i && Ds[j]==msf && (mask & 1<<Bs[j])
                || Ds[j]==f && Bs[j]==i && Cs[j]==msf && (mask & 1<<As[j]) )
                can_use = false;
            if( can_use )
               ID[make_pair(f,i)] = nextID[LR(f)]++;
         }
      }

      // then create the graph
      graph G( nextID[0] + nextID[1] );
      for(int j=0; j<As.size(); ++j)
      {
         pair<int,int> p(Cs[j], As[j]);
         pair<int,int> q(Ds[j], Bs[j]);
         if( ID.count(p) && ID.count(q) )
         {
            int pid = ID[p] + (LR(Cs[j]) ? nextID[0] : 0);
            int qid = ID[q] + (LR(Ds[j]) ? nextID[0] : 0);
            G[pid].push_back(qid);
            G[qid].push_back(pid);
         }
      }
      return make_pair(G, nextID[0]);
   }

   int maxGuards(int N, vector <string> escDescription) 
   {
      // parse the input
      vector<int> As, Bs, Cs, Ds, Ks(N);
      {
         stringstream sin;
         copy( escDescription.begin(), escDescription.end(), ostream_iterator<string>(sin,"") );

         for(int A,B,C; sin>>A>>B>>C; )
         {
            {char comma; sin>>comma;}
            --A, --B, --C; int D=(C+1)%N; // to 0-orign
            As.push_back(A);
            Bs.push_back(B);
            Cs.push_back(C);
            Ds.push_back(D);
            Ks[C] = max(Ks[C], A+1);
            Ks[D] = max(Ks[D], B+1);
         }
      }

      // the most simple floor, where the number Ks[msf] of stations is the least
      int msf = min_element(Ks.begin(), Ks.end()) - Ks.begin();

      // try all possibilities at the msf-th floor
      size_t answer = 0;
      for(int mask=0; mask<(1<<Ks[msf]); ++mask)
      {
         // then the rest of the part becomes a bipartite graph
         pair<graph, int> G = generateBipartiteGraph(As,Bs,Cs,Ds,Ks,msf,mask);

         // |MaxIndenepdentSet| == |V|-|MinCover| =(for bipartite graphs)= |V|-|MaxMatch|
         answer = max(answer, G.first.size() - biMatch<100>(G.first,G.second) + bitcnt(mask));
      }
      return answer;
   }
};