Решение на задачата "КОТКИ" от националния кръг на НОИ, 2013г. Използвана е имплементация на Edmond-Karp за Максимален поток в граф

MaxFlowEdmondKarp.cpp

#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int, int > ii;
struct Edge {
       int to, capacity, reverseEdgeIndex;
       Edge(int _t, int _c, int _r)
       {
        to = _t; capacity = _c; reverseEdgeIndex = _r;
       }
};
const int MAXR = 40;
const int MAXN = 2*MAXR*MAXR;
const int SOURCE = MAXN - 2;
const int SINK = MAXN-1;
const int INF = 1 << 27;
int N;
string matrix[MAXR];
vector<Edge> RG[MAXN];

int flow = 0;
bool visited[MAXN];
int parent[MAXN], parentEdge[MAXN];
vector<ii> getAdj(int x, int y)
{
     vector<ii> res;
     if(x - 1 >= 0) res.push_back(ii(x-1, y));
     if(x + 1 < N) res.push_back(ii(x+1, y));
     if(y-1 >= 0) res.push_back(ii(x, y-1));
     if(y+1 < matrix[0].size()) res.push_back(ii(x, y+1));
     return res;
}
int encode(int x, int y)
{
    return 2*(x*matrix[0].size() + y);
}
void construct()
{
 for(int i = 0; i < N; ++i)
 {
  for(int j = 0; j < matrix[i].size(); ++j)
  {
          //converting the vertex with capacity 1 to 2 vertexes with edge capacity of 1 between them
          RG[encode(i, j)].push_back(Edge(encode(i, j) + 1, 1, RG[encode(i, j) + 1].size()));
          RG[encode(i, j) + 1].push_back(Edge(encode(i, j), 0, RG[encode(i, j)].size()-1)); //adding a back edge

        //the cell is on the border of the field
          if(i == 0 || j == 0 || i == N-1 || j == matrix[0].size()-1)
          {
           //connect to sink
           RG[encode(i, j) + 1].push_back(Edge(SINK, INF, RG[SINK].size()));
           RG[SINK].push_back(Edge(encode(i, j) + 1, 0, RG[encode(i, j) + 1].size()- 1)); //adding a back edge
          }
          //there is a cat in the cell so we connect the SOURCE with it
          if(matrix[i][j] == '1')
          {
             //connect to source
             RG[SOURCE].push_back(Edge(encode(i, j), 1, RG[encode(i, j)].size()));
             RG[encode(i, j)].push_back(Edge(SOURCE, 0, RG[SOURCE].size()-1));
          }
          vector<ii> adj = getAdj(i, j);
          //going through all the adjacent cells
          for(int  k = 0; k < adj.size(); ++k)
          {
                   int childX = adj[k].first;
                   int childY = adj[k].second;
                   if(matrix[childX][childY] == '1') continue; //we add edges only to cells not preoccupied with cats
                   RG[encode(i, j) + 1].push_back(Edge(encode(childX, childY), 1, RG[encode(childX, childY)].size()));
                   RG[encode(childX, childY)].push_back(Edge(encode(i, j) + 1, 0, RG[encode(i, j) + 1].size() - 1)); //adding a back edge
          }
  }
 }
}
void BFS()
{
     memset(visited, 0, sizeof visited);
     memset(parent, -1, sizeof parent);
     queue<int> Q;
     Q.push(SOURCE);
     while(!Q.empty())
     {
          int current = Q.front(); Q.pop();
          for(int i = 0; i < RG[current].size(); ++i)
          {
                  int child = RG[current][i].to;
                  int capacity = RG[current][i].capacity;
                  if(!visited[child] && capacity > 0)
                  {
                        visited[child] = true;
                        Q.push(child);
                        parent[child] = current;
                        parentEdge[child] = i;
                        if(child == SINK) break;
                  }
          }
     }
}
void augment(int node, int minEdge)
{
     if(node == SOURCE)
     {
             flow = minEdge;
             return;
     }
     if(node == SINK && parent[SINK] == -1) return;
     augment(parent[node], min(minEdge, RG[parent[node]][parentEdge[node]].capacity)); //getting the capacity of the reverse edge
     RG[parent[node]][parentEdge[node]].capacity -= flow; //pushing flow through the current edge
     RG[node][RG[parent[node]][parentEdge[node]].reverseEdgeIndex].capacity += flow; //increasing the capacity of the reverse edge
}
int maxFlowEdmondKarp()
{
    int maxFlow = 0;
    while(true)
    {
          flow = 0;
          BFS();
          augment(SINK, INF);
          if(flow == 0) break;
          maxFlow += flow;
    }
    return maxFlow;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for(int i = 0; i < N; ++i)
    {
        cin >> matrix[i];
    }
    construct(); //construct the graph
    cout<<maxFlowEdmondKarp()<<'\n';
 return 0;
}
/*
3
0001
0110
1010


5
111010
000101
111101
111001
001000
*/