Pagini recente » Cod sursa (job #806518) | Cod sursa (job #1056198) | Cod sursa (job #2699630) | Cod sursa (job #2378460) | Cod sursa (job #2962558)
/*
* COmplexitate timp O(n * m^2)
*
* Algoritm folosit: Edmonds-Karp
*
* Am un graf cu n noduri in "partea stanga" si un graf cu n noduri in "partea dreapta".
* Am o muchie intre nodul i din partea stanga si nodul j din partea dreapta daca i != j, unde 1 <= i, j <= n.
*
* Practic am un graf bipartit cu n * (n - 1) muchii. Fiecare muchie are capacitatea 1.
*
* Creez o SuperSursa si un SuperSink.
*
* Pentru fiecare nod din partea stanga, creez o muchie de la SuperSursa la nodul respectiv. Capacitatea muchiei
* va fi corelata cu gradul de iesire al nodului respectiv.
*
* Pentru fiecare nod din partea dreapta, creez o muchie de la nodul respectiv la SuperSink. Capacitatea muchiei
* va fi corelata cu gradul de intrare al nodului respectiv.
*
* Aplic algoritmul de flux pe graful rezultat.
* In graful rezidual, muchiile saturate care pleaca din nodurile din partea stanga a grafului sunt muchiile care
* formeaza cuplajul maxim. Astfel, fluxul maxim este egal cu numarul de muchii din cuplajul maxim.
*
* Afisez muchiile care fac parte din cuplajul maxim.
*
* P.S.: implementarea este APROAPE identica cu cea din flux-max( exercitiul 1 ), aici folosesc matrice pentru flow
* si capacitate, cuplat cu lista de adiacenta a grafului, la flux-max folosesc lista de adiacenta pentru ID-ul muchiei
* si un vector de muchii.
* */
#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]) // muchie saturata sau vizitat
continue;
visited[neighbour] = true;
q.push(neighbour);
father[neighbour] = node;
if(neighbour == sink) // daca am ajuns la sink, am gasit un drum de ameliorare/crestere
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()
{
maxFlow = 0;
do{
if( !bfs() )
break;
for (auto nod : graph[sink]) {
if(capacity[nod][sink] == flow[nod][sink] || visited[nod] == 0) // muchie saturata sau nu am ajuns la nod
continue;
father[n] = nod;
int flowMin = 0x7fffffff;
for (int i = sink; i != source; 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 != source; 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) // partea stanga
for (int j = n/2; j <= n; ++j) // partea dreapta
if (flow[i][j] > 0) // muchie saturata
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;
}