Pagini recente » Cod sursa (job #1976014) | Cod sursa (job #2789685) | Cod sursa (job #297446) | Cod sursa (job #1705103) | Cod sursa (job #2766662)
#include <bits/stdc++.h>
#define NMAX 105
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n, c[2 * NMAX][2 * NMAX], F[2 * NMAX][2 * NMAX], t[2 * NMAX];
bitset <2 * NMAX> v;
queue <int> q;
vector <int> edges[2 * NMAX];
bool bfs()
{
bool ok = 0;
for(int i = 0 ; i <= 2 * n + 1; i++)
v[i] = 0;
v[0] = 1;
q.push(0);
while(!q.empty())
{
int nod = q.front();
q.pop();
for(auto k : edges[nod])
if(c[nod][k] - F[nod][k] > 0 && !v[k])
{
v[k] = 1;
t[k] = nod;
q.push(k);
if(k == 2 * n + 1)
ok = 1;
}
}
return ok;
}
int main()
{
f >> n;
for(int i = 1; i <= n; i++)
{
int x, y;
f >> x >> y;
c[0][i] = x;
c[i + n][2 * n + 1] = y;
edges[0].push_back(i);
edges[i].push_back(0);
edges[i + n].push_back(2 * n + 1);
edges[2 * n + 1].push_back(i + n);
for(int j = 1; j <= n; j++)
if(i != j)
{
c[i][j + n] = 1;
edges[i].push_back(j + n);
edges[j + n].push_back(i);
}
}
int minim, flux = 0;
while(bfs())
{
for(auto k : edges[2 * n + 1])
if(v[k] && c[k][2 * n + 1] > F[k][2 * n + 1])
{
minim = c[k][2 * n + 1] - F[k][2 * n + 1];
int p = k;
while(p)
{
minim = min(minim, c[t[p]][p] - F[t[p]][p]);
p = t[p];
}
flux += minim;
F[k][2 * n + 1] += minim;
F[2 * n + 1][k] -= minim;
p = k;
while(p)
{
F[t[p]][p] += minim;
F[p][t[p]] -= minim;
p = t[p];
}
}
}
g << flux << "\n";
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(F[i][n + j] == 1)
g << i << " " << j << "\n";
return 0;
}