## Thursday, January 1, 2015

### UVa Problem 10480 - Sabotage

Problem:

Solution:

Apparently, the problem asked for the min cut. During the last iteration of Edmonds Karp's, we already know the set of nodes reachable from source. That is one side of the cut, to find the cut edges, all we have to do is to go though all the edges, if one side of the edge is on the source and the another is not, then it is a cut edge.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1421

// #define LOG

#include "UVa10480.h"

#include <iostream>
#include <vector>
#include <set>
#include <queue>

using namespace std;

int UVa10480_Edmonds_Karps(vector<vector<int>>& capacities, vector<set<int>>& adjacency_list, int src, int dst);

int UVa10480()
{
while (true)
{
int number_of_nodes;
int number_of_edges;
cin >> number_of_nodes;
cin >> number_of_edges;

if (number_of_nodes == 0 && number_of_edges == 0)
{
break;
}

vector<vector<int>> capacities;
capacities.resize(number_of_nodes);
for (int src = 0; src < number_of_nodes; src++)
{
capacities[src].resize(number_of_nodes);
for (int dst = 0; dst < number_of_nodes; dst++)
{
capacities[src][dst] = 0;
}
}

for (int e = 0; e < number_of_edges; e++)
{
int src;
int dst;
int cost;
cin >> src;
cin >> dst;
cin >> cost;

// Input is 1 based index
src--;
dst--;

capacities[src][dst] += cost;

capacities[dst][src] += cost;
}

}

return 0;
}

int UVa10480_Edmonds_Karps(vector<vector<int>>& capacities, vector<set<int>>& adjacency_list, int src, int dst)
{
int total_flow = 0;
// Step 2: Edmonds Karp's
vector<int> parents; // Allow back-tracking the path found from bfs
int number_of_nodes = parents.size();
parents.resize(number_of_nodes); // avoid reallocation
while (true)
{
// Step 2.1: Use BFS to find an augmenting flow
queue<int> bfs_queue;
for (int n = 0; n < number_of_nodes; n++)
{
parents[n] = -1; // indicating the node is not enqueued
}

parents[src] = -2; // indicating the node is enqueued but no actual parent because this is the root
bfs_queue.push(src);
while (bfs_queue.size() > 0)
{
int current = bfs_queue.front();
bfs_queue.pop();
{
int neighbor = *ni;
if (parents[neighbor] == -1 && capacities[current][neighbor] > 0)
{
parents[neighbor] = current;
bfs_queue.push(neighbor);

if (neighbor == dst)
{
break;
}
}
}
if (parents[dst] != -1)
{
break;
}
}

if (parents[dst] == -1)
{
break;
}
else
{
// We have found an augmenting path, go through the path and find the max flow through this path
int cur = dst;
bool first = true;
int max_flow_through_path = 0;
while (true)
{
int src = parents[cur];
if (src != -2)
{
int dst = cur;
int available = capacities[src][dst];
#ifdef LOG
cout << src << "--" << available << "->" << dst << endl;
#endif
cur = parents[cur];
if (first)
{
max_flow_through_path = available;
first = false;
}
else
{
max_flow_through_path = min(max_flow_through_path, available);
}
}
else
{
break;
}
}
#ifdef LOG
cout << "flowing " << max_flow_through_path << endl << endl;
#endif
total_flow += max_flow_through_path;
// Flow the max flow through the augmenting path
cur = dst;
while (true)
{
int src = parents[cur];
if (src != -2)
{
capacities[src][cur] -= max_flow_through_path;
capacities[cur][src] += max_flow_through_path;
cur = parents[cur];
}
else
{
break;
}
}
}
}
#ifdef LOG
cout << "The total flow is " << total_flow << endl;
#endif
}

{
set<int> source_side;
int number_of_nodes = parents.size();
for (int i = 0; i < number_of_nodes; i++)
{
if (parents[i] == -2 || parents[i] >= 0)
{
source_side.insert(i);
// These are reachable nodes, belongs to left hand side of the edge.
}
}
#ifdef LOG
cout << "Source side of the cut" << endl;
for (set<int>::iterator si = source_side.begin(); si != source_side.end(); si++)
{
cout << *si << " ";
}
cout << endl;
#endif
for (set<int>::iterator si = source_side.begin(); si != source_side.end(); si++)
{
int s = *si;
{
int n = *ni;
if (source_side.find(n) == source_side.end())
{
cout << (s + 1) << " " << (n + 1) << endl;
}
}
}
cout << endl;
}

#### 1 comment :

1. Thanks a lot, it's was helpful to me :)