Pagini recente » Cod sursa (job #835714) | Cod sursa (job #1864549) | Cod sursa (job #202347) | Cod sursa (job #650131) | Cod sursa (job #2968693)
// C++ implementation of Dinic's Algorithm
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
struct Edge
{
int v;
int flow;
int C;
int rev;
};
// Residual Graph
class Graph
{
public:
int V; // number of vertex
vector<int> level; // stores level of a node
vector< vector<Edge> >adj;
public:
Graph(int V)
{
adj = vector<vector<Edge>>(V);
this->V = V;
level = vector<int>(V);
}
// add edge to the graph
void addEdge(int u, int v, int C)
{
// Forward edge : 0 flow and C capacity
Edge a{v, 0, C, (int) adj[v].size()};
// Back edge : 0 flow and 0 capacity
Edge b{u, 0, 0, (int) adj[u].size()};
adj[u].push_back(a);
adj[v].push_back(b); // reverse edge
}
bool BFS(int s, int t);
int sendFlow(int s, int flow, int t, int ptr[]);
int DinicMaxflow(int s, int t);
};
// Finds if more flow can be sent from s to t.
// Also assigns levels to nodes.
bool Graph::BFS(int s, int t)
{
for (int i = 0; i < V; i++)
level[i] = -1;
level[s] = 0;
list<int> q;
q.push_back(s);
vector<Edge>::iterator i;
while (!q.empty())
{
int u = q.front();
q.pop_front();
for (auto &e: adj[u])
{
if (level[e.v] < 0 && e.flow < e.C)
{
level[e.v] = level[u] + 1;
q.push_back(e.v);
}
}
}
return level[t] < 0 ? false : true;
}
int Graph::sendFlow(int u, int flow, int t, int start[])
{
if (u == t)
return flow;
for (; start[u] < adj[u].size(); start[u]++)
{
Edge &e = adj[u][start[u]];
if (level[e.v] == level[u] + 1 && e.flow < e.C)
{
int curr_flow = min(flow, e.C - e.flow);
int temp_flow
= sendFlow(e.v, curr_flow, t, start);
if (temp_flow > 0)
{
e.flow += temp_flow;
adj[e.v][e.rev].flow -= temp_flow;
return temp_flow;
}
}
}
//failed to find the target
return 0;
}
int Graph::DinicMaxflow(int s, int t)
{
if (s == t)
return -1;
int total = 0;
while (BFS(s, t) == true)
{
int *start = new int[V + 1]{0};
while (int flow = sendFlow(s, INT_MAX, t, start))
total += flow;
}
return total;
}
int main()
{
int n;
int x, y, c;
fin >> n;
Graph g(n * 2 + 2);
for (int i = 1; i <= n; i++)
{
fin >> x >> y;
g.addEdge(0, i, x);
g.addEdge(n + i, 2 * n + 1, y);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
if (j == i)
continue;
g.addEdge(i, j + n, 1);
}
fout << g.DinicMaxflow(0, 2 * n + 1) << "\n";
for(int i = 1; i <= n; i++)
{
for(auto &edge: g.adj[i])
{
if (edge.flow == edge.C && edge.C > 0)
fout << i << " " << edge.v - n<< "\n";
}
}
return 0;
}