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();

}

## No comments:

## Post a Comment