Pagini recente » Cod sursa (job #246904) | Cod sursa (job #8387) | Cod sursa (job #617803) | Cod sursa (job #3155660) | Cod sursa (job #3194250)
#include <climits>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
vector<vector<int>> adj;
int cap[2005][2005], tata[2005], n, m, s, t;
bool bfs()
{
queue <int> q;
vector <bool> vizitat(n * 2 + 2, false);
q.push(s);
vizitat[s] = true;
tata[s] = -1;
while (!q.empty())
{
int nod = q.front();
q.pop();
for (auto vecin : adj[nod])
{
if (!vizitat[vecin] && cap[nod][vecin] != 0)
{
tata[vecin] = nod;
if (vecin == t)
return true;
vizitat[vecin] = true;
q.push(vecin);
}
}
}
return false;
}
int maxflow() //Alg. Edmonds Karp
{
int maxim = 0;
while (bfs())
{
int b, a = t, flow = INT_MAX;
while (a != s)
{
b = tata[a];
if (cap[b][a] < flow)
flow = cap[b][a];
a = b;
}
a = t;
while (a != s)
{
b = tata[a];
cap[b][a] -= flow;
cap[a][b] += flow;
a = b;
}
maxim += flow;
}
return maxim;
}
int main()
{
int a, b, i, j;
fin >> n;
t = n * 2 + 1; //sink
adj.resize(t + 1);
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
if (i != j)
{
adj[i].push_back(j + n);
adj[j + n].push_back(i);
cap[i][j + n] = 1;
}
}
fin >> a >> b;
adj[s].push_back(i);
adj[i].push_back(s);
cap[s][i] = a;
adj[t].push_back(i + n);
adj[i + n].push_back(t);
cap[i + n][t] = b;
}
fout << maxflow() << endl;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
if (cap[j + n][i] == 1)
fout << i << " " << j << endl;
}
}
return 0;
}