fork download 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. long maxFlow = 0, startSum = 0, targetSum = 0;
  6.  
  7. class Graph;
  8. class Edge;
  9. int valence(char atom);
  10. int findBackEdge(Graph *G, Edge edge);
  11.  
  12. class Edge {
  13. public:
  14.     int from;
  15.     int to;
  16.     int flow;
  17.  
  18.     Edge(int from=-1, int to=-1, int flow=0);
  19. };
  20.  
  21. class Graph {
  22.  
  23. public:
  24.     int v_num;
  25.     int height;
  26.     int width;
  27.     vector<bool> checked;
  28.     vector<vector<Edge> > edge;
  29.  
  30.     Graph(int height, int width);
  31.     void addEdge(int from, int to, int flow);
  32.     void init(int height, int width);
  33.     void uncheckAll();
  34.     int toVertNum(int i, int j);
  35. };
  36.  
  37. Graph::Graph(int height, int width) {
  38.     this->height = height;
  39.     this->width = width;
  40.     this->v_num = height * width + 2;
  41.     checked.resize(v_num, false);
  42.     edge.resize(v_num);
  43. }
  44.  
  45. int findBackEdge(Graph *G, Edge edge) {
  46.     for(int child = 0; child < G->edge[edge.to].size(); ++child)
  47.         if(G->edge[edge.to][child].to == edge.from) {
  48.             return child;
  49.         }
  50.     return -1;
  51. }
  52.  
  53. int valence(char atom) {
  54.     switch(atom) {
  55.         case('H'):
  56.             return 1;
  57.         case('O'):
  58.             return 2;
  59.         case('N'):
  60.             return 3;
  61.         case('C'):
  62.             return 4;
  63.     }
  64.     return 0;
  65. }
  66.  
  67. void Graph::addEdge(int from, int to, int flow = 1) {
  68.     edge[from].push_back(
  69.             Edge(from, to, flow)
  70.         );
  71. }
  72.  
  73. void Graph::uncheckAll() {
  74.     for(int i=0; i < v_num; ++i)
  75.         checked[i] = false;
  76. }
  77.  
  78. int Graph::toVertNum(int i, int j) {
  79.     return i * width + j + 1;
  80. }
  81.  
  82. void Graph::init(int height, int width) {
  83.     for (int i = 0; i < height; i++)
  84.         for (int j = 0; j < width; j++) {
  85.             char atom;
  86.             cin >> atom;
  87.             if ( (i%2 + j%2)%2 == 0 ) {
  88.                 addEdge(0, toVertNum(i,j), valence(atom));
  89.                 startSum += valence(atom);
  90.                 if (i + 1 < height)
  91.                     addEdge (toVertNum(i,j), toVertNum(i+1,j));
  92.                 if (j + 1 < width)
  93.                     addEdge (toVertNum(i,j), toVertNum(i,j+1));
  94.                 if (i - 1 >= 0)
  95.                     addEdge (toVertNum(i,j), toVertNum(i-1,j));
  96.                 if (j - 1 >= 0)
  97.                     addEdge (toVertNum(i,j), toVertNum(i,j-1));
  98.             }
  99.             else {
  100.                 addEdge(toVertNum(i,j), v_num - 1, valence(atom));
  101.                 targetSum += valence(atom);
  102.             }
  103.         }
  104. }
  105.  
  106. Edge::Edge(int from, int to, int flow) {
  107.     this->from = from;
  108.     this->to = to;
  109.     this->flow = flow;
  110. }
  111.  
  112. int tryPushFlow(Graph *G, int current = 0, int capacity = 5) {
  113.     G->checked[current] = true;
  114.     if(current == G->v_num-1) {
  115.         maxFlow += capacity;
  116.         return capacity;
  117.     }
  118.     for(int e=0; e < G->edge[current].size(); ++e) {
  119.         Edge edge = G->edge[current][e];
  120.  
  121.         if(G->checked[edge.to] || edge.flow == 0)
  122.             continue;
  123.  
  124.         int minCapacity = tryPushFlow(G, edge.to, min(edge.flow, capacity));
  125.         if(minCapacity > 0) {
  126.             G->edge[current][e].flow -= minCapacity;
  127.             int backEdgeNum = findBackEdge(G, edge);
  128.             if (backEdgeNum != -1)
  129.                 G->edge[edge.to][backEdgeNum].flow += minCapacity;
  130.             else
  131.                 G->edge[edge.to].push_back(Edge(edge.to, current, minCapacity));
  132.             return minCapacity;
  133.         }
  134.     }
  135.     return 0;
  136. }
  137.  
  138. int main() {
  139.     int height, width;
  140.     cin >> height >> width;
  141.     Graph G = Graph(height, width);
  142.     G.init(height, width);
  143.  
  144.     while(tryPushFlow(&G))
  145.         G.uncheckAll();
  146.  
  147.     (maxFlow == startSum) && (maxFlow == targetSum) && (maxFlow != 0) ?
  148.     cout << "Valid" : cout << "Invalid";
  149. }
Success #stdin #stdout 0s 5548KB
comments (?)
stdin 
2
3
HNH
OHO
stdout 
Invalid
https://ideone.com/eR9aTm
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!