Pagini recente » Cod sursa (job #1914032) | Cod sursa (job #1626953) | Cod sursa (job #1598640) | Cod sursa (job #557396) | Cod sursa (job #2661122)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n,i,j,x,y,resid[205][205],tata[205];
vector<int> L[205];
deque<int> c;
bitset<205> f;
bool bfs()
{
f.reset(); f[0] = 1; c.push_back(0); tata[0] = -1;
while (!c.empty())
{
int nod = c.front(); c.pop_front();
for (int i=0; i<L[nod].size(); i++)
{
int vecin = L[nod][i];
if (!f[vecin] && resid[nod][vecin] > 0)
{
c.push_back(vecin);
f[vecin] = 1; tata[vecin] = nod;
}
}
}
return f[2*n+1];
}
int main()
{
fin >> n;
for (i=1; i<=n; i++)
{
fin >> x >> y;
L[0].push_back(i);
L[i].push_back(0);
resid[0][i] = x;
L[2*n+1].push_back(n+i);
L[n+i].push_back(2*n+1);
resid[n+i][2*n+1] = y;
}
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
if (i != j)
{
L[i].push_back(n+j);
L[n+j].push_back(i);
resid[i][n+j] = 1;
}
int flow = 0;
while (bfs())
for (i=0; i<L[2*n+1].size(); i++)
{
int vecin = L[2*n+1][i];
if (f[vecin] && resid[vecin][2*n+1] > 0)
{
int path_flow = resid[vecin][2*n+1];
while (vecin != 0)
{
path_flow = min(path_flow, resid[tata[vecin]][vecin]);
vecin = tata[vecin];
}
vecin = L[2*n+1][i];
resid[vecin][2*n+1] -= path_flow;
resid[2*n+1][vecin] += path_flow;
while (vecin != 0)
{
resid[tata[vecin]][vecin] -= path_flow;
resid[vecin][tata[vecin]] += path_flow;
vecin = tata[vecin];
}
flow += path_flow;
}
}
fout << flow << "\n";
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
if (i != j && resid[i][n+j] == 0)
fout << i << " " << j << "\n";
return 0;
}