Pagini recente » Cod sursa (job #2720783) | Cod sursa (job #2222535) | Cod sursa (job #1347896) | Cod sursa (job #589554) | Cod sursa (job #1435761)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int n, m, F[210][210], C[210][210], S, D, pred[210], maxflow;
vector <int> G[210];
queue <int> Q;
bool Accesibil()
{
int i, x;
vector <int>::iterator it;
for(i = 1; i <= D; ++i)
pred[i] = -1;
pred[S] = 0;
Q.push(S);
while(!Q.empty())
{
x = Q.front();
Q.pop();
for(it = G[x].begin(); it != G[x].end(); ++it)
{
if(pred[*it] == -1 && F[x][*it] < C[x][*it])
{
pred[*it] = x;
Q.push(*it);
}
}
}
if(pred[D] == -1)
return false;
return true;
}
void MaxFlow()
{
int x, val;
vector <int>::iterator it;
while(Accesibil())
{
for(it = G[D].begin(); it != G[D].end(); ++it)
{
if(F[*it][D] >= C[*it][D])
continue;
x = *it;
val = C[x][D] - F[x][D];
while(pred[x])
{
val = min(val, C[pred[x]][x] - F[pred[x]][x]);
x = pred[x];
}
maxflow += val;
x = *it;
F[x][D] += val;
F[D][x] -= val;
while(pred[x])
{
F[pred[x]][x] += val;
F[x][pred[x]] -= val;
x = pred[x];
}
}
}
}
int main()
{
int i, j, nrin, nrout;
ifstream fin("harta.in");
fin >> n;
for(i = 1; i <= n; ++i)
{
for(j = 1; j <= n; ++j)
{
if(i == j)
continue;
G[i].push_back(j + n);
G[j + n].push_back(i);
C[i][j + n] = 1;
}
}
S = 2 * n + 1;
D = 2 * n + 2;
for(i = 1; i <= n; ++i)
{
fin >> nrout >> nrin;
G[S].push_back(i);
G[i].push_back(S);
C[S][i] = nrout;
G[i + n].push_back(D);
G[D].push_back(i + n);
C[i + n][D] = nrin;
}
fin.close();
MaxFlow();
ofstream fout("harta.out");
m = maxflow;
fout << m << "\n";
for(i = 1; i <= n; ++i)
{
for(j = 1; j <= n; ++j)
{
if(i == j)
continue;
if(F[i][j + n] == 1)
fout << i << ' ' << j << "\n";
}
}
fout.close();
return 0;
}