Pagini recente » Autentificare | Cod sursa (job #1359920) | Cod sursa (job #1900802) | Cod sursa (job #966084) | Cod sursa (job #2959964)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
class Flow
{
int source, sink;
int n;
int maxFlow;
std::vector<bool> visited;
std::vector<std::vector<int> > graph;
std::vector<std::vector<int> > capacity;
std::vector<std::vector<int> > flow;
std::vector<int> father;
void dfs(int x) {
visited[x] = true;
for (int node : graph[x]) {
if (!visited[node] && flow[x][node] < capacity[x][node]) {
dfs(node);
}
}
}
bool bfs()
{
visited.assign(n+1, false);
std::queue<int> q;
q.push(source);
visited[source] = true;
while(!q.empty())
{
int node = q.front();
q.pop();
for(int neighbour : graph[node])
{
if(capacity[node][neighbour] == flow[node][neighbour] || visited[neighbour])
continue;
visited[neighbour] = true;
q.push(neighbour);
father[neighbour] = node;
if(neighbour == sink)
return true;
}
}
return false;
}
public:
Flow(int n, int source, int sink)
{
this->source = source;
this->sink = sink;
this->n = n;
this->maxFlow = 0;
capacity.resize(n + 1, std::vector<int>(n + 1));
flow.resize(n + 1, std::vector<int>(n + 1));
graph.resize(n + 1);
visited.resize(n + 1);
father.resize(n + 1);
}
void addEdge(int x, int y, int cost = 1)
{
if(capacity[x][y] == 0)
{
graph[x].push_back(y);
graph[y].push_back(x);
}
capacity[x][y] += cost;
}
int getMaxFlow()
{
int maxFlow = 0;
do{
if( !bfs() )
break;
for (auto nod : graph[n]) {
if(capacity[nod][n] == flow[nod][n] || visited[nod] == 0)
continue;
father[n] = nod;
int flowMin = 0x7fffffff;
for (int i = sink; i; i = father[i])
flowMin = std::min(flowMin, capacity[father[i]][i] - flow[father[i]][i]);
if (flowMin == 0)
continue;
maxFlow += flowMin;
for (int i = sink; i; i = father[i]) {
flow[father[i]][i] += flowMin;
flow[i][father[i]] -= flowMin;
}
}
} while (true);
return maxFlow;
}
int getFlow() const{
return maxFlow;
}
std::vector<std::pair<int, int>> getMinCut()
{
visited.assign(n+1, false);
for (int i = 1; i <= n/2; ++i) {
flow[source][i] = 0;
}
dfs(source);
std::vector<std::pair<int, int>> minCut;
for (int i = source; i <= sink; ++i) {
for (int j : graph[i]) {
if (visited[i] && !visited[j] && capacity[i][j] > 0)
minCut.emplace_back(i, j);
}
}
return minCut;
}
void printGraph() {
for (int i = 1; i <= n/2; ++i)
for (int j = n/2; j <= n; ++j)
if (flow[i][j] > 0)
out << i << ' ' << j - n/2 << '\n';
}
};
int main() {
int n;
in >> n;
Flow f(2 * n + 1, 0, 2 * n + 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i != j)
f.addEdge(i, j + n);
int x, y;
for (int i = 1; i <= n; ++i) {
in >> x >> y;
f.addEdge(0, i, x);
f.addEdge(n + i, 2 * n + 1, y);
}
in.close();
int sol = f.getMaxFlow();
out << sol << '\n';
f.printGraph();
out.close();
return 0;
}