I checked out a couple of solutions from the leaderboard and it seems that lot of them are using the following max-flow algorithm:

- we create a new graph where original vertices are duplicated (vertex i becomes 2*i and 2*i+1)
- if i and j vertices were connected in original graph then 2*i and 2*j+1 plus 2*j and 2*i+1 gets connected in new graph with capacity 1
- source vertex (S) is connected to each 2*i vertex with capacity min(T, degree)
- each 2*i+1 vertex is connected to target vertex (T) with capacity 1
- max-flow gives the answer

I was trying to come up with a similar flow-based solution but it's always seemed wrong. I realize that the above algorithm always gives the correct answer but I just cannot see why.

Could someone explain why this works? Thx!

These resources may help. It will take some time to learn max-flow concepts.

http://nptel.ac.in/courses/106101060/23

https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-section-1/

https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-section-2/

Input format section states "Note that the graph doesn't have parallel edges or loops.", but testcase 2 has loops in given graph. What am I missing?

C++ solution, passes all test cases. Same algorithm as most of the other top-voted comments in this thread: Constructs bipartite graph with source, sink, and two regions, which we can call A and B, each with N nodes (the number in the original crab graph), then uses Ford-Fulkerson to find the max flow (with BFS to find paths in the residual network) as described in Chapter 26.2 of CLRS introduction to algorithms. Each edge in the original crab graph corresponds to two symmetric edges between A and B, and has capacity 1. Also, every node in region B has a capacity 1 edge to the sink. Finally, the source has an edge of capacity min(T, degree(a)) to each node in region a, where T is the max number of legs a crab can have, and degree(a) is the number of edges coming out of node a into region B.

At first, it seems non-obvious why max flow is equivalent to the number of nodes covered by crabs, but if you think about it for a while, it makes sense: because each b in region B has a capacity 1 edge going to the sink, that means each b can have at most 1 nonzero flow edge going into it from region A; in other words, each node can belong to at most one crab. Additionally, setting the source to a capacities to min(T, degree(a)) limits the number of legs each crab has to T. Hence, the flow into the crab head nodes in region A is the same as the number of leg nodes in the optimal crab graph. Finally, the number of heads are also included, since there are also head nodes in region B, which will receive 1 flow from one of its legs in region A. Hence, the max flow of this setup is exactly equal to the number of nodes covered by the optimal crab graph.

#include <iostream>
#include <vector>
#include <deque>

using std::vector;
using std::deque;
using Matrix=vector<vector<int>>;

int residual_capacity(const Matrix &cap, const Matrix &flow, int from, int to){
  if(cap[from][to]) return cap[from][to]-flow[from][to];
  else if(cap[to][from]) return flow[to][from]; 
  else return 0;
}

vector<int> residual_path(const Matrix &cap, const Matrix &flow){
  const int no_parent=-2, unvisited=-1;
  const int source=cap.size()-2,sink=source+1;
  vector<int> parent(sink+1,unvisited);
  parent[source]=no_parent;
  deque<int> bfs;
  vector<int> path;
  bfs.push_back(source);
  while(!bfs.empty()){
    int i=bfs.front(); bfs.pop_front();
    for(int j=0;j<cap.size();++j){
      if(parent[j]==unvisited){
	if(residual_capacity(cap,flow,i,j)){
	  if(j==sink){
	    path.push_back(sink);
	    int par=i;
	    while(par!=no_parent){
	      path.push_back(par);
	      par=parent[par];
	    }
	    return path;
	  }else{
	    parent[j]=i;
	    bfs.push_back(j);
	  }
	}
      }	
    }
  }
  return path;
}

Matrix max_flow(const Matrix &cap){
  const int source=cap.size()-2,sink=source+1;
  Matrix flow(sink+1,vector<int>(sink+1,0));
  auto path=residual_path(cap,flow);
  while(!path.empty()){
    int min_cap=cap.size();
    for(int j=0;j<path.size()-1;++j){
      int res_cap=residual_capacity(cap,flow,path[j+1],path[j]);
      if(res_cap<min_cap) min_cap=res_cap;
    }
    for(int j=0;j<path.size()-1;++j){
      if(cap[path[j+1]][path[j]]) flow[path[j+1]][path[j]] += min_cap;
      else flow[path[j]][path[j+1]] -= min_cap;
    }
    path=residual_path(cap,flow);
  }
  return flow;
}

int solve(Matrix &cap){
  const int source=cap.size()-2,nnode=source/2;
  auto flow=max_flow(cap);
  int total=0;
  for(int i=0;i<nnode;++i){
    if(flow[source][2*i]!=0){
      total+=flow[source][2*i];
    }
  }
  return total;
}

void input_case(){
  int nnode=0, nfeet=0, nedge=0;
  std::cin >> nnode >> nfeet >> nedge;
  const int source=2*nnode, sink=source+1;
  Matrix cap(sink+1,vector<int>(sink+1,0));
  while(nedge--){
    int i=0, j=0;
    std::cin >> i >> j; --i; --j;
    cap[2*i][2*j+1]=1;
    cap[2*j][2*i+1]=1;
    ++cap[source][2*i];
    ++cap[source][2*j];
  }
  for(int i=0;i<nnode;++i){
    cap[2*i+1][sink]=1;
    if(cap[source][2*i]>nfeet){
      cap[source][2*i]=nfeet;
    }
  }
  std::cout << solve(cap) << '\n';
}

int main(){
  int ncase=0;
  std::cin >> ncase;
  while(ncase--) input_case();
}

Theoretical Analysis of the Crab Problem

Problem Definition A crab is an undirected graph which has two kinds of vertices: 1 head, and K feet , and exactly K edges which join the head to each of the feet.( 1≤K≤T , where T is given) Given an undirected graph, you have to find in it some vertex-disjoint subgraphs where each one is a crab. The goal is to select those crabs in such a way that the total number of vertices covered by them is maximized.

Algorithm First above, we put forward an algorithm that gives the answer of this tricky question. We will prove its property later. The algorithm states as below. We have the original diagram as shown in Fig.1(There are only four nodes for simplicity) We transform the picture into the one below by expanding the i^th node to the node pair of 〖2i〗^th,〖2i+1〗^th. And the edges of that crab between node (i,j) is now transformed into the edges of (2i,2j+1),(2j,2i+1), we set the capacity as 1. Then we add the Sender and Receiver nodes. We set the capacity from Sender to 2i as T, and we set the capacity from 2i+1 to Receiver as 1. Here we compute this max-flow problem and get the answer.

Proof. Before proofing, we set some rules for easier illustration. We denote the answer of the crab problem as Crab Answer, and call the answer of the max-flow problem as the Max-Flow Answer. In fact, both question may have several different answers (in the combinatory sense), but in fact any of them only have one answer as the consequence, which is no more than a number, S. What we want to do is to prove that given a Crab Answer, we can construct from it a Max-Flow answer, so that we can prove these two question have the same consequence S. In order to prove this claim, we know that we should have a Crab Answer first. For example, in Fig3. We have got the Crab Answer. We know the Crab Answer has the following properties: The head is connected to several legs and the number of legs won’t surpass K. The different crabs do not share any nodes. The number of vertices is maximized.

We will use these properties in the following proof. However, we can change it into an available flow solution like in Fig4. The construction of an available flow solution goes like this: For each crab, we let the flow from its head to its legs. We also choose a flow from one of its legs to its head. We will let the according flow from Sender to the heads, and those from the heads and legs to the Receiver.

Since the crabs are vertex-disjoint and the leg number can be no less than 1, so it is always effective.

Now we’ve constructed an available flow, and for the first constraint of a Crab Answer, the flow from Sender to any of the 2i node won’t exceed K. So the flow constraint is well obeyed.

In this way, we proved that, the Crab Answer will get a sequence CC no more than the Max-Flow Answer FC, since an available answer will never exceed the maximum answer. CC≤FC.

Then we will prove the Max-Flow Answer also will not exceed the Crab Answer. FC≤CC. In this proof, we will use the third constraint of the Crab Answer.

In fact, the available flow we’ve constructed above will always be a valid flow. And more insight into it will also prove that it is also a max flow.

In order to prove this, we will use the conclusion that Largest flow, FC is equal to the Smallest cut, SC. So we want to prove that this available flow is also a cut. If we’ve proved that the available flow is a cut, then we have CC≥AC=FC.

Suppose it is not a cut, then there should exist a path between the Sender and Receiver, we denote this path as S→2i→2j+1→R, and this path do not include any path that’s already used. Using the constraint of Crab Answer, we know that the node of 2j+1 won’t be head or leg, the paths from heads or legs to the Receive are all already used. So2j+1 should be a blank node.

Then the node of 2i can only be three kinds of vertices. Blank node In this way, there exists a path between two blank nodes, which is not acceptable because this disobeys the third constraint of Crab Answer. Leg node In this case, if number of legs≥2, then no matter if the leg node is connected to the second layer head node or not, we can always get it disconnected from that node by using other leg nodes to connect the second layer header node if needed Then we can detach the leg and form a new crab of this leg node and blank node, which disobeys the third law of Crab Answer. However, if number of legs=1, then we can call either of the two nodes as head, and the new blank node can also be included, which disobeys the third law of a Crab Answer. Head node In this case, in order to make sure the path won’t counteract with that from the S to 2i, the legs of that header shouldn’t have been fully occupied, in this way, we can add the blank node as the header’s legs, which also disobeyed the third law of a Crab Answer. In this sense, we know that the Crab Answer can be transformed into a Cut, which guarantees that CC≥FC, and in 1), we’ve got CC≤FC. So CC=FC.

In this way, we know that the crab consequence is the same with the max-flow consequence.

Codes (in C++)

include

include

using namespace std;

const int Maxn=300; int pre[Maxn]; int v[Maxn]; int g[Maxn][Maxn]; int f[Maxn][Maxn];
int min(const int val1,const int val2)
{
return val1 }
int maxFlow()
{
for(int i=0;i {
for(int i=0;i que;
pre[s]=s;
v[s]=0x7fffffff; que.push(s);
while(!que.empty())
{
queTop=que.front();
que.pop();
for(int i=0;i {
if(pre[i]<0) {
if(g[queTop][i]>f[queTop][i])
{
v[i]=min(g[queTop][i]-f[queTop][i],v[queTop]); pre[i]=queTop; que.push(i);

                }  
                if(f[i][queTop]>0)  
                {  
                    v[i]=min(f[i][queTop],v[queTop]);  
                    pre[i]=queTop+n; 
                    que.push(i);  
                }  
            }  
        }  
        if(pre[t]>=0) break;  
    }  
    if(pre[t]<0) break; 
    int p=0,q=t;  
    int minval=v[t];  
    while(q!=s)  
    {  
        p=pre[q];  

        if(p>=n)  
        {  
            p-=n;  
            f[q][p]-=minval;            }  
        else  
            f[p][q]+=minval;            q=p;  
    }  
}  
queTop=0;  
for(int i=0;i<n;++i)   
    queTop+=f[s][i];  
return queTop;  

}

int main()
{
int C; cin >> C; for(int i=0;i