TC SRM447 D1 500 (PeopleYouMayKnow)

The problem statement can be accessed via:
http://www.topcoder.com/stat?c=problem_statement&pm=10580

The problem itself is pretty simple: it asks us to given a friends graph determine the number of friends to remove such that there are no paths from friend A to friend B which has a length less than 3.

The key observation is to remove all friends which have a shortest path between A and B which exceeds 3 as these will never conflict with our objective. To determine intermediate distances we can just use Floyd-Warshall's algorithm to calculate all-pairs shortest paths between friends. Then we can discard any nodes which violate dist[person1][i] + dist[i][person2] <= 3. Note that the problem fixes the constraint to not allow any paths with a length of less than 3 - this allows us to use a simple bipartite matching to determine the minimum cut of the network. For the general problem of having a length less than n, we can simply use a network flow algorithm (which we use for the implementation here).

We can divide the friends into two (one used as an in-node, the other used as an out-node) and run the maximum flow algorithm over the network. This concept is very similar to the one used in TC SRM360 D1 500 (Prince of Persia).

Implementation below:

class PeopleYouMayKnow {
public:
  int maximalScore(vector <string>, int, int);
};

int augment(int cur, int flow, int ret);

int adjmat[201][201];
int used[201][201];
bool visited[201];
int t;

int maxflow() {
  int flow = 0, thisFlow = 0;
  memset(visited,false,sizeof(visited));
  while ((thisFlow = augment(0, INT_MAX-1, 0)) != 0) {
    memset(visited,false,sizeof(visited));
    flow += thisFlow;
  }
  return flow;
}

int augment(int cur, int flow, int ret) {
  if (cur == t-1) return flow;
  visited[cur] = true;
  for (int i = 0; i < t && ret == 0; i++) {
    if (adjmat[cur][i] > used[cur][i] && !visited[i] && 
      (ret = augment(i, min(flow,adjmat[cur][i]-used[cur][i]), 0)) > 0)
      used[cur][i] += ret;
    else if (used[i][cur] > 0 && !visited[i] && 
      (ret = augment(i,min(flow, used[i][cur]), 0)) > 0)
      used[i][cur] -= ret;
  }
  return ret;
}

int distTable[51][51];
int validNodes[51];
#define INF (1<<20)

int PeopleYouMayKnow::maximalScore(vector <string> friends, int A, int B) {
  int res = 0;
  int sz = friends.size();
  for (int i = 0; i < sz; i++)
    for (int j = 0; j < sz; j++)
      if (i == j) distTable[i][j] = 0;
      else distTable[i][j] = friends[i][j] == 'Y' ? 1 : INF;
  for (int k = 0; k < sz; k++)
    for (int i = 0; i < sz; i++)
      for (int j = 0; j < sz; j++)
        distTable[i][j] <?= distTable[i][k] + distTable[k][j];
  // build the network - allowing infinite capacities between 
  // out -> in nodes and restricting capacities between nodes with 1 capacity
  for (int i = 0; i < sz; i++)
    for (int j = 0; j < sz; j++)
      if (friends[i][j] == 'Y')
        adjmat[i+1+sz][j+1] = INF;
  for (int i = 0; i < sz; i++)
    if (distTable[person1][i] + distTable[i][person2] > 3)
      for (int j = 0; j < sz; j++) adjmat[j+1][i+1] = adjmat[i+1][j+1] = 0;
    else
      validNodes[i] = 1;
  for (int i = 0; i < sz; i++)
    if (validNodes[i]) adjmat[i+1][i+1+sz] = 1; else adjmat[i+1][i+1+sz] = 0;
  adjmat[0][person1+1] = INF;
  adjmat[person1+1][person1+1+sz] = INF;
  adjmat[person2+1][person2+1+sz] = INF;
  adjmat[person2+1+sz][2*sz+1] = INF;
  t = 2*sz+2;
  return res = maxflow();
}