Pagini recente » Cod sursa (job #321797) | Cod sursa (job #344732) | Cod sursa (job #265865) | Cod sursa (job #101495) | Cod sursa (job #2962886)
/*
Algoritm: Folosim Edmonds Karp pentru flow maxim cu BFS
- afisam doar muchiile saturate
-----> Complexitatea = O(n*m^2)
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define N 202
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, flow, maxflow, i, j, a, b, sink, cnode;
pair<int, int> nod;
vector<int> graph[N];
int capac[N][N];
int tata[N];
bool viz[N];
bool BFS()
{
queue<pair <int, int>> myq;
memset(tata, 0, (sink+1) * sizeof(int));
memset(viz, false, (sink+1) * sizeof(bool));
myq.push({0, INT_MAX});
viz[0] = true;
while(!myq.empty())
{
nod = myq.front();
myq.pop();
for(auto &vecin: graph[nod.first]){
if(!viz[vecin] && capac[nod.first][vecin] > 0)
{
tata[vecin] = nod.first;
viz[vecin] = true;
flow = min(nod.second, capac[nod.first][vecin]);
if(vecin == sink)
return true;
myq.push({vecin, flow});
}
}
}
flow = 0;
return false;
}
int main() {
fin >> n;
sink = 2 * n + 1;
for(i = 1; i <= n; ++i){
fin >> a >> b;
graph[0].push_back(i);
graph[i].push_back(0);
capac[0][i] = a;
graph[n+i].push_back(sink);
graph[sink].push_back(n+i);
capac[n+i][sink] = b;
}
for(i = 1; i<= n; ++i){
for(j = n + 1; j < sink; ++j){
if(j - i == n)
continue;
capac[i][j] = 1;
graph[i].push_back(j);
graph[j].push_back(i);
}
}
while(BFS())
{
maxflow += flow;
cnode = sink;
while(cnode){
capac[cnode][tata[cnode]] += flow;
capac[tata[cnode]][cnode] -= flow;
cnode = tata[cnode];
}
}
fout << maxflow << '\n';
for(i = 1; i <= n; ++i){
for(j = n + 1; j < sink; ++j){
if(capac[j][i] == 1)
fout << i << ' ' << j - n << '\n';
}
}
return 0;
}