Pagini recente » Istoria paginii utilizator/prichindel | Monitorul de evaluare | Istoria paginii utilizator/simion-constantinescu_andrei_323ca | Atasamentele paginii alinieri | Cod sursa (job #3332209)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
const int nmax = 205;
vector <int> g[nmax];
int n, in[nmax], out[nmax];
int rez;
int cap[nmax][nmax], flow[nmax][nmax], t[nmax];
bool viz[nmax];
bool bfs (int s, int dest)
{
for (int i = 0; i <= 2 * n + 1; i++)
viz[i] = false;
queue <int> q;
viz[s] = true;
q.push (s);
while (!q.empty ())
{
int node = q.front ();
q.pop ();
for (auto x : g[node])
{
if (!viz[x] && cap[node][x] - flow[node][x] > 0)
{
viz[x] = true;
t[x] = node;
q.push (x);
}
}
}
return viz[2 * n + 1];
}
void compute_flow (int s, int dest)
{
while (bfs (s, dest))
{
int sum = 1000;
for (int i = dest; i != 0; i = t[i])
sum = min (sum, cap[t[i]][i] - flow[t[i]][i]);
for (int i = dest; i != 0; i = t[i])
{
flow[t[i]][i] += sum;
flow[i][t[i]] -= sum;
}
}
}
int main ()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> out[i] >> in[i];
for (int i = 1; i <= n; i++)
{
g[0].push_back (i);
g[i].push_back (0);
cap[0][i] = in[i];
g[2 * n + 1].push_back (i + n);
g[i + n].push_back (2 * n + 1);
cap[i + n][2 * n + 1] = out[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i != j)
{
g[j].push_back (i + n);
g[i + n].push_back (j);
cap[j][i + n] = 1;
}
}
}
compute_flow (0, 2 * n + 1);
vector <pair <int, int>> rez;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && cap[j][i + n] - flow[j][i + n] == 0)
rez.push_back ({i, j});
fout << rez.size () << '\n';
for (auto it : rez)
fout << it.first << " " << it.second << '\n';
return 0;
}