Pagini recente » Cod sursa (job #761724) | Cod sursa (job #200266) | Cod sursa (job #961129) | Cod sursa (job #1525754) | Cod sursa (job #1443583)
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
int n, s, nod, in[101], out[101], m[101][101], v[101];
int C[205][205],F[205][205] ;
vector<int> G[205];
int maxflow = 0;
int tata[205];
int bfs(int s)
{
queue<int>q;
for (int i = 0; i <= n; i++)
{
tata[i] = -1;
}
tata[s] = 0;
q.push(s);
while (!q.empty())
{
int x = q.front();
for (int i = 0; i < G[x].size(); i++)
{
if (tata[G[x][i]] == -1 && F[x][G[x][i]] != C[x][G[x][i]])
q.push(G[x][i]);
tata[i] = x;
}
}
if (tata[n] == -1)
return 0;
return 1;
}
void Maxflow()
{
int D = n;
while (bfs(0))
{
for (vector<int>::iterator it = G[D].begin(); it != G[D].end(); it++)
{
if (F[*it][D] == C[*it][D])
continue;
int val = C[*it][D] - F[*it][D];
int crt = *it;
while (tata[crt])
{
val = min(val, C[tata[crt]][crt] - F[tata[crt]][crt]);
crt= tata[crt];
}
maxflow += val;
F[*it][D] += val;
F[D][*it] -= val;
crt = *it;
while (tata[crt])
{
F[tata[crt]][crt] += val;
F[crt][tata[crt]] -= val;
crt = tata[crt];
}
}
}
}
int main()
{
ifstream fin("harta.in");
ofstream fout("harta.out");
fin >> n;
for (int i = 1; i <= n; i++)
{
int innr, outnr;
fin >> innr >> outnr;
G[0].push_back(i);
G[i].push_back(0);
C[0][i] = innr;
G[i + n].push_back(2 * n + 1);
G[2 * n + 1].push_back(i + n);
C[i + n][2 * n + 1] = outnr;
for (int j = 1; j <= n; j++)
{
if (i != j)
{
G[i].push_back(n + j);
G[j + n].push_back(i);
C[i][j + n] = 1;
}
}
}
int nr = n;
n = 2 * n + 1;
Maxflow();
fout << maxflow<<'\n';
for (int i = 1; i <= nr; i++)
{
for (int j = 1; j <= nr; j++)
{
if (i != j&&F[i][j + n] == 1)
fout << i << ' ' << j << '\n';
}
}
}