Select Git revision
euklides-odcitaci.py
-
Martin Mareš authored
Též přesunuty příklady, které přetekly z 01.
Martin Mareš authoredTéž přesunuty příklady, které přetekly z 01.
group-connectivity.h 3.58 KiB
#ifndef __GROUP_CONNECTIVITY_H__
#define __GROUP_CONNECTIVITY_H__
#include <vector>
#include "options.h"
#include "rings.h"
#include "fast-array.h"
typedef int EdgeId;
typedef int DirectedEdgeId;
typedef std::pair<DirectedEdgeId, DirectedEdgeId> TwoCut;
struct AbstractTester {
bool isConnected;
#if SAVE_MEMORY
typedef std::vector<bool> ClassesType;
#else
typedef std::vector<size_t> ClassesType;
#endif
ClassesType classes;
virtual void init(
int edges,
std::vector<EdgeId> spanningTree,
std::vector<TwoCut> twoCuts,
std::vector< std::vector<DirectedEdgeId> > elementaryCycles
) =0;
virtual std::vector<size_t> getClasses() =0;
virtual bool run() =0;
virtual ~AbstractTester() {}
};
template < typename Ring_ >
struct Tester : public AbstractTester {
typedef Ring_ Ring;
typedef typename Ring::T T;
typedef ::Mapping<Ring> Mapping;
size_t numForb;
int edges;
std::vector<EdgeId> classEdges;
std::vector< std::pair<EdgeId, Mapping> > nonClassEdges;
virtual void init(
int edges_,
std::vector<EdgeId> spanningTree,
std::vector<TwoCut> twoCuts,
std::vector< std::vector<DirectedEdgeId> > elementaryCycles
) {
edges = edges_;
numForb = 1;
while (edges_-- > 0) numForb *= (Ring::size - 1);
size_t num_classes = 1;
edges_ = spanningTree.size();
while (edges_-- > 0) num_classes *= Ring::size;
ClassesType C(num_classes, 0);
C.swap(classes);
for (auto e : spanningTree)
classEdges.push_back(e - 1);
for (const auto& elemCycle : elementaryCycles) {
nonClassEdges.push_back(std::make_pair(elemCycle[0] - 1, Mapping(edges)));
Mapping &map = nonClassEdges.back().second;
for (auto edge : elemCycle) {
bool neg = (edge < 0);
edge = neg ? -edge : edge;
edge -= 1;
map.assign(edge, neg ? Ring::one : Ring::negate(Ring::one));
}
}
}
#if USE_NEXT_FORB
bool nextForb(Mapping& forb) {
for (size_t i = 0; i < edges; i++) {
T v = forb[i] + 1;
if (v >= Ring::size) {
forb.assign(i, 1);
} else {
forb.assign(i, v);
return true;
}
}
return false;
}
#else // !USE_NEXT_FORB
Mapping& unpack(size_t index, Mapping& ret) {
size_t m = Ring::size - 1;
for (size_t i = 0; i < edges; i++) {
ret.assign(i, (index % m) + 1);
index /= m;
}
return ret;
}
#endif
Mapping& cannonize(Mapping& map) {
for (const auto &i : nonClassEdges) {
#if OPTIMIZE_COMBINE
if (map[i.first] != Ring::zero)
#endif
map.combine(map[i.first], i.second);
}
return map;
}
size_t pack(const Mapping& map) {
size_t index = 0;
for (auto i : classEdges) {
index *= Ring::size;
index += map[i];
}
return index;
}
virtual std::vector<size_t> getClasses() {
#if SAVE_MEMORY
std::vector<size_t> ret(classes.size());
for (size_t i = 0; i < classes.size(); i++) ret[i] = classes[i];
return ret;
#else
return classes;
#endif
}
virtual bool run() {
# if SAVE_MEMORY
# define INC(a) a = true
# else
# define INC(a) a++
# endif
Mapping forb(edges);
# if USE_NEXT_FORB
for (size_t i = 0; i < edges; i++) forb.assign(i, 1);
do {
Mapping copy(forb);
INC(classes[pack(cannonize(copy))]);
} while (nextForb(forb));
# else
for (size_t i = 0; i < numForb; i++)
INC(classes[pack(cannonize(unpack(i, forb)))]);
# endif
for (const auto &c : classes) if (!c) return (isConnected = false);
return (isConnected = true);
# undef INC
}
virtual ~Tester() {}
};
#endif