// Pornim de la descrierea soluției problemei, înspre rezolvarea problemei.
//
// O pereche (S₁, S₂) este soluție a problemei G=(V,E) dacă:
// ▪ S₁ ⊆ V ⊂ ℤ
// ▪ S₂ ⊆ V ⊂ ℤ
// ▪ ∀ e ∈ E ( ( ∃ x ∈ S₁ ( Muchia e iese din vârful x. ) )
// ∨ ( ∃ y ∈ S₂ ( Muchia e intră în vârful y. ) )
// )
// ▪ |S₁ ∪ S₂| este minim.
//
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Pornind de la G = (V,E), construim graful bipartit G₃ = (V₃, E₃).
// G₃ = { V₃, E₃ }
// ▪ V₁ = V × {0}
// ▪ V₂ = V × {1}
// ▪ V₃ = V₁ ∪ V₂
// ▪ E₃ ⊆ V₁ × V₂
// ▪ ( (x,0), (y,1) ) ∈ E₃ ⇔ ( (x,y) ∈ E )
// ▪ |E₃| este minim.
//
// O pereche (T₁,T₂) este soluție a problemei G₃ dacă:
// ▪ T₁ ⊆ V₁
// ▪ T₂ ⊆ V₂
// ▪ T₁ ∪ T₂ este o acoperire cu vârfuri a muchiilor grafului G
// ( T₁ ∪ T₂ is a vertex cover )
// ( adică:
// ∀ e ∈ E ∃ v ∈ T₁ ∪ T₂ ( e is incident with v )
// )
// ▪ |T₁ ∪ T₂| este minim ( T₁ ∪ T₂ is a minimum size vertex cover )
//
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Dacă (S₁, S₂) este soluție a problemei G
// , atunci T₁ ∪ T₂ este soluție a problemei G₃.
// , unde T₁ = S₁ × {0}, T₂ = S₂ × {1}.
//
// Invers, dacă T₁ ∪ T₂ este soluție a problemei G₃
// , iar S₁ și S₂ sunt două mulțimi astfel încât T₁ = S₁ × {0} și T₂ = S₂ × {1}
// , atunci (S₁, S₂) este soluție a problemei G.
//
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
// For a bipartite graph, the size of a minimum vertex cover is equal to the
// size of a maximum matching. A minimum vertex cover may be obtained from
// taking the left endpoint of each edge of a maximum matching. ( The matching
// M is for a graph G=(L ∪ R, E), where E ⊆ L × R, L is left, and R is right. ).
// In any finite bipartite graph, a maximum matching may be computed with
// Hopcroft-Karp algorithm, in O((√n)·m) time, where n=|V|, m=|E|, and G=(V,E) is
// the graph for which the matching is computed.
//
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
// Rezolvăm problema G, rezolvând problema G₃.
//
// _______________________________________________________________________________
#include <cstddef>
#include <set>
#include <vector>
#include <fstream>
#include <iostream>
#include <sstream>
// _______________________________________________________________________________
/// \brief Finds the maximum size matching of the bipartite graph
/// Uses the Hopcroft-Karp algorithm.
///
/// http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm
class HopcroftKarp
{ private:
::std::size_t const m_n0;
::std::size_t const m_n2;
::std::vector< ::std::vector< ::std::size_t > > const & m_adj2;
::std::size_t m_nil;
::std::size_t m_inf;
::std::vector< ::std::size_t > m_pair0;
::std::vector< ::std::size_t > m_pair2;
::std::vector< ::std::size_t > m_dist;
::std::vector< ::std::size_t > m_queue;
::std::vector< ::std::size_t > & m_visited;
::std::size_t m_maxSize;
public:
/// \brief Computes maximum size matching for bipartite graph.
HopcroftKarp
( ::std::size_t const n0
, ::std::size_t const n2
, ::std::vector< ::std::vector < ::std::size_t > > const & adj2
)
;
private:
/// \brief Acquires space.
void
acquireSpace
()
;
/// \brief Computes matching.
void
solve
()
noexcept
;
/// \brief Computes matching.
bool
bfs
()
noexcept
;
/// \brief Computes matching.
bool
dfs
( ::std::size_t const v0
)
noexcept
;
public:
/// \brief Gives access to answer.
::std::size_t
getMaxSize
()
const
noexcept
;
/// \brief Gives access to answer.
::std::vector< ::std::size_t> const &
getPair0
()
const
noexcept
;
/// \brief Gives access to answer.
::std::vector< ::std::size_t> const &
getPair2
()
const
noexcept
;
} // class HopcroftKarp
;
HopcroftKarp::
HopcroftKarp
( ::std::size_t const n0
, ::std::size_t const n2
, ::std::vector< ::std::vector < ::std::size_t > > const & adj2
)
: m_n0(n0)
, m_n2(n2)
, m_adj2(adj2)
, m_visited(m_queue)
{ // Let use make a note on the 'm_visited(m_queue)' above.
// The m_queue vector is used by the BFS. The DFS is performed after the BFS.
// The DFS reuses the m_queue vector. To keep the code readable, we make a
// reference.
acquireSpace();
// no-throw, no-fail
solve();
}
void
HopcroftKarp::
acquireSpace
()
{ ::std::vector< ::std::size_t> tmpPair0(m_n0);
::std::vector< ::std::size_t> tmpPair2(m_n2);
::std::vector< ::std::size_t> tmpDistance(m_n0);
::std::vector< ::std::size_t> tmpQueue(m_n0);
::std::size_t const maxn02 =
((m_n0 > m_n2) ? m_n0 : m_n2);
// no-throw, no-fail
m_nil = maxn02;
m_inf = m_n0; // ∞ only needs to be an upper bound for values
// in the queue ( m_queue ).
m_pair0.swap(tmpPair0);
m_pair2.swap(tmpPair2);
m_dist.swap(tmpDistance);
m_queue.swap(tmpQueue);
}
void
HopcroftKarp::
solve
()
noexcept
{ // Start with the empty matching.
::std::size_t v0;
for(v0 = 0; m_n0 > v0; ++v0)
{ m_pair0[v0] = m_nil; }
::std::size_t v2;
for(v2 = 0; m_n2 > v2; ++v2)
{ m_pair2[v2] = m_nil; }
// Improve matching.
m_maxSize = 0;
bool existsAugmentingPath =
bfs();
while(existsAugmentingPath)
{ // Augment.
for(v0 = 0; m_n0 > v0; ++v0)
{ m_visited.at(v0) = 0; }
for(v0 = 0; m_n0 > v0; ++v0)
{ if(m_nil == (m_pair0.at(v0) ) )
{ if(true == (dfs(v0) ) )
{ ++m_maxSize;
}
}
}
// Search for augmenting paths.
existsAugmentingPath = bfs();
}
// Now, processing is complete.
}
bool
HopcroftKarp::
bfs
()
noexcept
{ ::std::size_t qOut = 0; // Queue out.
::std::size_t qIn = 0; // Queue in.
::std::size_t v0; // Vertex from partition zero.
for(v0 = 0; m_n0 > v0; ++v0)
{ if(m_nil == (m_pair0.at(v0) ) )
{ m_queue.at(qIn) = v0;
++qIn;
m_dist.at(v0) = 0;
}
else
{ m_dist.at(v0) = m_inf; }
}
::std::size_t distOfNil = m_inf; // 'dist[nil] = ∞'
::std::size_t distOfV0;
while(qOut < qIn)
{ v0 = m_queue.at(qOut);
++qOut;
distOfV0 = m_dist.at(v0);
if(distOfNil > distOfV0)
{ ::std::vector< ::std::size_t > const & adj = m_adj2.at(v0);
for( ::std::size_t const v2 : adj )
{ ::std::size_t const x0 = m_pair2.at(v2);
if(m_nil != x0)
{ if(m_inf == (m_dist.at(x0) ) )
{ m_dist.at(x0) = (1 + distOfV0);
m_queue.at(qIn) = x0;
++qIn;
}
}
else
{ if(m_inf == distOfNil)
{ distOfNil = (1 + distOfV0);
}
}
}
}
}
bool const existsAugmentingPath =
(m_inf != distOfNil);
return existsAugmentingPath;
}
bool
HopcroftKarp::
dfs
( ::std::size_t const v0
)
noexcept
{ m_visited.at(v0) = 1;
::std::vector< ::std::size_t > const & adj =
m_adj2.at(v0);
for( ::std::size_t const v2 : adj )
{ ::std::size_t const x0 = m_pair2.at(v2);
if(m_nil != x0)
{ if(0 == (m_visited.at(x0) ) )
{ if( (1 + (m_dist.at(v0) ) ) == (m_dist.at(x0) ) )
{ if(true == dfs(x0) )
{ m_pair0[v0] = v2;
m_pair2[v2] = v0;
return true; // Augmenting path.
}
}
}
}
else
{ m_pair0[v0] = v2;
m_pair2[v2] = v0;
return true; // Augmenting path.
}
}
return false; // No augmenting path.
}
::std::size_t
HopcroftKarp::
getMaxSize
()
const
noexcept
{ return m_maxSize;
}
::std::vector< ::std::size_t> const &
HopcroftKarp::
getPair0
()
const
noexcept
{ return m_pair0;
}
::std::vector< ::std::size_t> const &
HopcroftKarp::
getPair2
()
const
noexcept
{ return m_pair2;
}
// _______________________________________________________________________________
void
logErrorMessage
( char const * pErrorMessage
)
{ if(nullptr == pErrorMessage)
{ pErrorMessage = "Error in error message.";
}
::std::cerr << pErrorMessage << ::std::endl;
}
// _______________________________________________________________________________
/// \brief Computes a minimum vertex cover from a maximum matching in a
/// bipartite graph.
///
/// Uses the argument used in following proof:
/// http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29
class VertexCoverFromMatchingInBipartiteGraph
{ private:
/// \brief The bipartite graph G=(V₁∪V₂, E). |V₁|.
::std::size_t const m_n0;
/// \brief The bipartite graph G=(V₁∪V₂, E). |V₂|.
::std::size_t const m_n2;
/// \brief The bipartite graph |E|.
::std::vector< ::std::vector< ::std::size_t > > const & m_adj2;
/// \brief The maximum matching M. M is a matching in G.
/// M is given by pairs of vertices in V₁.
///
/// If some vertex x ∈ V₁ is not matched, then 'm_pair0[x] == nil'
/// , where nil == ::std::max(m_n0, m_n1).
::std::vector< ::std::size_t > const & m_pair0;
/// \brief The maximum matching M. M is a matching in G.
::std::vector< ::std::size_t > const & m_pair2;
/// \brief The vertex cover. This is what is to be computed.
::std::vector< ::std::size_t > & m_vertexCover;
/// \brief The transpose.
::std::vector< ::std::vector< ::std::size_t > > m_trAdj2;
/// \brief The queue array.
::std::vector< ::std::size_t > m_queue;
/// \brief The distance array.
/// Vertices with the same distance are in the same level.
/// The level is what the wikipedia page talks about.
::std::vector< ::std::size_t > m_distance;
/// \brief The vertex cover. Temporary, until swapped.
::std::vector< ::std::size_t > m_tmpVertexCover;
/// \brief The vertex cover size.
::std::size_t m_vertexCoverSize;
/// \brief The nil (in the matching).
::std::size_t m_nil;
/// \brief The ∞ distance.
::std::size_t m_distInfinity;
/// \brief The queue out position.
::std::size_t m_queueOut;
/// \brief The queue in position.
::std::size_t m_queueIn;
/// \brief Status.
bool m_ok;
public:
/// \brief Computes the minimum vertex cover.
VertexCoverFromMatchingInBipartiteGraph
( ::std::size_t const n0
, ::std::size_t const n2
, ::std::vector< ::std::vector< ::std::size_t > > const & adj2
, ::std::vector< ::std::size_t > const & pair0
, ::std::vector< ::std::size_t > const & pair2
, ::std::vector< ::std::size_t > & vertexCover
, ::std::size_t & vertexCoverSize
, bool & ok
)
;
private:
/// \brief Computes the minimum vertex cover using the method described in
/// the wikipedia proof for Kőnig's Theorem.
bool
computeMinimumSizeVertexCover
()
;
/// \brief Acquires space for computing the minimum vertex cover.
bool
acquireSpaceForMinimumSizeVertexCover
()
;
/// \brief Computes the the minimum vertex cover.
/// Space is already acquired. Success is guaranteed.
void
processMinimumSizeVertexCover
()
noexcept
;
/// \brief Queue unmatched vertices.
void
queueUnmatchedVertices
()
noexcept
;
/// \brief Even level is the last added level into the queue.
/// Add next odd level, into the queue.
void
processEvenLevel
()
noexcept
;
/// \brief Odd level is the last added level into the queue.
/// Add next even level, into the queue.
void
processOddLevel
()
noexcept
;
/// \brief Queue neighbours of left partition vertex.
void
queueNeighboursOfLeftPartitionVertex
( ::std::size_t const x
)
noexcept
;
/// \brief Queue neighbours of right partition vertex.
void
queueNeighboursOfRightPartitionVertex
( ::std::size_t const y
)
noexcept
;
/// \brief Queue neighbours of right partition vertex.
void
extractMinimumVertexCover
()
noexcept
;
} // class VertexCoverFromMatchingInBipartiteGraph
;
VertexCoverFromMatchingInBipartiteGraph::
VertexCoverFromMatchingInBipartiteGraph
( ::std::size_t const n0
, ::std::size_t const n2
, ::std::vector< ::std::vector< ::std::size_t > > const & adj2
, ::std::vector< ::std::size_t > const & pair0
, ::std::vector< ::std::size_t > const & pair2
, ::std::vector< ::std::size_t > & vertexCover
, ::std::size_t & vertexCoverSize
, bool & ok
)
: m_n0(n0)
, m_n2(n2)
, m_adj2(adj2)
, m_pair0(pair0)
, m_pair2(pair2)
, m_vertexCover(vertexCover)
, m_ok(computeMinimumSizeVertexCover() )
{ ok = m_ok;
if( !ok)
{ return; } // Failure. The called logged.
// no-throw, no-fail
vertexCover.swap(m_tmpVertexCover);
vertexCoverSize = m_vertexCoverSize;
m_vertexCoverSize = 0;
}
bool
VertexCoverFromMatchingInBipartiteGraph::
computeMinimumSizeVertexCover
()
{ bool ok;
ok = acquireSpaceForMinimumSizeVertexCover();
if( !ok)
{ return false; } // Failure. The called logged.
processMinimumSizeVertexCover();
return true; // Success.
}
bool
VertexCoverFromMatchingInBipartiteGraph::
acquireSpaceForMinimumSizeVertexCover
()
{ bool ok;
// Acquire transpose.
::std::vector< ::std::vector< ::std::size_t > > tmpTrAdj2(m_n2);
::std::size_t x;
for(x = 0; m_n0 > x; ++x)
{ ::std::vector< ::std::size_t > const & adj =
m_adj2.at(x);
for( ::std::size_t const & y : adj )
{ tmpTrAdj2.at(y).push_back(x);
}
}
::std::size_t const n = (m_n0 + m_n2);
ok = ( (n >= m_n0) && ( (n - m_n0) >= m_n0) );
if( !ok)
{ logErrorMessage("implementation limit");
return false; // Failure.
}
::std::size_t const tmpDistInfinity = n;
::std::size_t const tmpMin =
( (m_n0 < m_n2) ? m_n0 : m_n2 );
::std::vector< ::std::size_t > tmpQueue(n);
::std::vector< ::std::size_t > tmpDistance(n, tmpDistInfinity);
::std::vector< ::std::size_t > tmpMinimumVertexCover(tmpMin);
// no-throw, no-fail
m_trAdj2.swap(tmpTrAdj2);
m_queue.swap(tmpQueue);
m_distance.swap(tmpDistance);
m_tmpVertexCover.swap(tmpMinimumVertexCover);
m_distInfinity = n;
return true; // Success.
}
void
VertexCoverFromMatchingInBipartiteGraph::
processMinimumSizeVertexCover
()
noexcept
{ m_queueIn = 0;
m_queueOut = 0;
m_nil = ( (m_n0 > m_n2) ? m_n0 : m_n2);
queueUnmatchedVertices();
while(m_queueOut < m_queueIn)
{ processEvenLevel();
processOddLevel();
}
extractMinimumVertexCover();
}
void
VertexCoverFromMatchingInBipartiteGraph::
queueUnmatchedVertices
()
noexcept
{ ::std::size_t x;
::std::size_t y;
::std::size_t z;
// Add unmatched vertices from V₁.
for(x=0; m_n0 > x; ++x)
{ if(m_nil == m_pair0.at(x) )
{ m_distance.at(x) = 0;
m_queue.at(m_queueIn) = x;
++m_queueIn;
}
}
// Add unmatched vertices from V₂.
for(y=0; m_n2 > y; ++y)
{ if(m_nil == m_pair2.at(y) )
{ z = (m_n0 + y);
m_distance.at(z) = 0;
m_queue.at(m_queueIn) = z;
++m_queueIn;
}
}
}
void
VertexCoverFromMatchingInBipartiteGraph::
processEvenLevel
()
noexcept
{ ::std::size_t z;
::std::size_t const queueIn0 =
m_queueIn;
while(m_queueOut < queueIn0)
{ z = m_queue.at(m_queueOut);
++m_queueOut;
if(z < m_n0)
{ queueNeighboursOfLeftPartitionVertex(z);
}
else
{ queueNeighboursOfRightPartitionVertex(z-m_n0);
}
}
}
void
VertexCoverFromMatchingInBipartiteGraph::
processOddLevel
()
noexcept
{ ::std::size_t z;
::std::size_t x;
::std::size_t y;
::std::size_t z2;
::std::size_t dist;
::std::size_t const queueIn0 =
m_queueIn;
while(m_queueOut < queueIn0)
{ z = m_queue.at(m_queueOut);
++m_queueOut;
if(m_n0 > z)
{ x = z;
y = m_pair0.at(x);
z2 = m_n0 + y;
}
else
{ y = z - m_n0;
x = m_pair2.at(y);
z2 = x;
}
dist = m_distance.at(z);
m_distance.at(z2) = (1+dist);
m_queue.at(m_queueIn) = z2;
++m_queueIn;
}
}
void
VertexCoverFromMatchingInBipartiteGraph::
queueNeighboursOfLeftPartitionVertex
( ::std::size_t const x
)
noexcept
{ ::std::vector< ::std::size_t > const & adj =
m_adj2.at(x);
for( ::std::size_t const & y : adj )
{ ::std::size_t const z = (m_n0 + y);
if(m_distInfinity == m_distance.at(z) )
{ m_distance.at(z) = (1 + m_distance.at(x) );
m_queue.at(m_queueIn) = z;
++m_queueIn;
}
}
}
void
VertexCoverFromMatchingInBipartiteGraph::
queueNeighboursOfRightPartitionVertex
( ::std::size_t const y
)
noexcept
{ ::std::size_t const z = (m_n0 + y);
::std::vector< ::std::size_t > const & adj =
m_trAdj2.at(y);
for( ::std::size_t const & x : adj )
{ if(m_distInfinity == m_distance.at(x) )
{ m_distance.at(x) = (1 + m_distance.at(z) );
m_queue.at(m_queueIn) = x;
++m_queueIn;
}
}
}
void
VertexCoverFromMatchingInBipartiteGraph::
extractMinimumVertexCover
()
throw()
{ m_vertexCoverSize = 0;
::std::size_t t;
::std::size_t z;
::std::size_t d;
for(t = 0; m_queueIn > t; ++t)
{ z = m_queue.at(t);
d = m_distance.at(z);
if(0 != (d % 2) )
{ m_tmpVertexCover.at
(m_vertexCoverSize) = z;
++m_vertexCoverSize;
}
}
::std::size_t x;
::std::size_t y;
::std::size_t d2;
for(x=0; m_n0 > x; ++x)
{ y = m_pair0.at(x);
if(m_nil != y)
{ y += m_n0;
d = m_distance.at(x);
d2 = m_distance.at(y);
if( (m_distInfinity == d )
&& (m_distInfinity == d2 )
)
{ m_tmpVertexCover.at
(m_vertexCoverSize) = x;
++m_vertexCoverSize;
}
}
}
}
// _______________________________________________________________________________
::std::size_t const max_n = 8191;
::std::size_t const max_m = 20000;
/// \brief Reads question.
class QuestionReader
{ private:
::std::size_t & m_n;
::std::size_t & m_m;
::std::vector< ::std::vector < ::std::size_t > > & m_adj2;
bool const m_ok;
public:
/// \brief Question is input.
QuestionReader
( bool & ok
, ::std::size_t & n
, ::std::size_t & m
, ::std::vector < ::std::vector < ::std::size_t > > & adj2
)
;
private:
/// \brief Read.
bool
readBipartiteGraph
()
;
} // class QuestionReader
;
QuestionReader::
QuestionReader
( bool & ok
, ::std::size_t & n
, ::std::size_t & m
, ::std::vector < ::std::vector < ::std::size_t > > & adj2
)
: m_n(n)
, m_m(m)
, m_adj2(adj2)
, m_ok(readBipartiteGraph() )
{ ok = m_ok;
}
bool
QuestionReader::
readBipartiteGraph
()
{ ::std::size_t n;
::std::size_t m;
::std::ifstream is("felinare.in");
is >> n >> m;
bool ok;
ok = ( ( (1 <= n) && (max_n >= n) )
&& ( (1 <= m) && (max_m >= m) )
)
;
if( !ok)
{ logErrorMessage("bad input: (n, m)");
return false; // Failure.
}
::std::vector
< ::std::vector< ::std::size_t > >
adj2(n);
::std::size_t t;
::std::size_t x;
::std::size_t y;
for(t=0; m>t; ++t)
{ is >> x >> y;
ok = ( ( (1 <= x) && (x <= n) )
&& ( (1 <= y) && (y <= n) )
&& ( x != y )
)
;
if( !ok)
{ logErrorMessage("bad input: (x, y)");
return false; // Failure.
}
// With duplicated edges the algorithm works correctly.
// The performance is a little bit encumbered.
--x;
--y;
adj2.at(x).push_back(y);
}
ok = (! (is.fail() ) );
if( !ok)
{ logErrorMessage("Bad input: input stream");
return false; // Failure.
}
// no-throw, no-fail
m_n = n;
m_m = m;
m_adj2.swap(adj2);
return true; // Success.
}
// _______________________________________________________________________________
/// \brief http://www.infoarena.ro/problema/felinare
class Felinare
{ private:
/// \brief Input graph G=(V,E). |V|.
::std::size_t m_n;
/// \brief Input graph G=(V,E). |E|.
::std::size_t m_m;
/// \brief Input graph G=(V,E). E.
::std::vector< ::std::vector< ::std::size_t > > m_adj2;
/// \brief Output. # de becuri aprinse.
::std::size_t m_ans0;
/// \brief Starea becurilor din vârfuri.
::std::vector< ::std::size_t > m_ans2;
/// \brief Status.
bool const m_ok;
public:
/// \brief Do all.
Felinare
( bool & ok
)
;
private:
/// \brief Do all.
bool
solve
()
;
/// \brief Read input.
bool
readQuestion
()
;
/// \brief Solve problem.
bool
computeAnswer
()
;
/// \brief Write answer.
bool
writeAnswer
()
;
} // class Felinare
;
Felinare::
Felinare
( bool & ok
)
: m_ok(solve() )
{ ok = m_ok;
}
bool
Felinare::
solve
()
{ bool ok;
ok = readQuestion();
if( !ok)
{ return false; } // Failure. The called logged.
ok = computeAnswer();
if( !ok)
{ return false; } // Failure. The called logged.
ok = writeAnswer();
if( !ok)
{ return false; } // Failure. The called logged.
return true; // Success.
}
bool
Felinare::
readQuestion
()
{ bool ok;
QuestionReader reader(ok, m_n, m_m, m_adj2);
if( !ok)
{ return false; } // Failure. The called logged.
return true; // Success.
}
bool
Felinare::
computeAnswer
()
{ bool ok;
// Build the auxiliary graph.
::std::size_t const n0 = m_n;
::std::size_t const n2 = m_n;
::std::vector
< ::std::vector < ::std::size_t >
> const & adj2 = m_adj2;
// Compute maximum matching for auxiliary graph.
HopcroftKarp theAlgorithm(n0, n2, adj2);
// Compute minimum vertex cover from the maximum matching.
::std::vector< ::std::size_t > const & pair0 =
theAlgorithm.getPair0();
::std::vector< ::std::size_t > const & pair2 =
theAlgorithm.getPair2();
::std::vector< ::std::size_t > vertexCover;
::std::size_t vertexCoverSize;
VertexCoverFromMatchingInBipartiteGraph
theProcessing
( n0, n2, adj2
, pair0, pair2
, vertexCover
, vertexCoverSize
, ok
);
if( !ok)
{ return false; } // Failure. The called logged.
// Compute answer from minimum vertex cover.
::std::size_t ans0 = (m_n + m_n);
ok = ((ans0 >= m_n) && ((ans0 - m_n) >= m_n));
if( !ok)
{ logErrorMessage("Implementation limit.");
return false; // Failure.
}
ans0 -= vertexCoverSize;
::std::vector< ::std::size_t > ans2(m_n, 3);
::std::size_t t;
::std::size_t z;
::std::size_t x;
::std::size_t y;
for(t = 0; vertexCoverSize > t; ++t)
{ z = vertexCover.at(t);
if(n0 > z)
{ x = z;
ans2.at(x) -= 1;
}
else
{ y = (z - n0);
ans2.at(y) -= 2;
}
}
// no-throw, no-fail
m_ans0 = ans0;
m_ans2.swap(ans2);
return true; // Success.
}
bool
Felinare::
writeAnswer
()
{ ::std::ofstream os("felinare.out");
os << m_ans0 << ::std::endl;
::std::size_t x;
::std::size_t f;
for(x=0; m_n > x; ++x)
{ f = (m_ans2.at(x) );
os << f << ::std::endl;
}
os.close();
bool ok;
ok = os.good();
if( !ok)
{ logErrorMessage("output error.");
return false; // Failure.
}
return true; // Success.
}
// _______________________________________________________________________________
bool
solveFelinare
()
{ bool ok;
Felinare problem(ok);
if( !ok)
{ return false; } // Failure. The called logged.
return true; // Success.
}
// _______________________________________________________________________________
int
main()
{ int status;
try
{ bool const ok = solveFelinare();
status = ( ok ? 0 : 1 );
}
catch ( ... )
{ status = 2;
}
return status;
}
Marius B mgnt