Pagini recente » Cod sursa (job #3180541) | Cod sursa (job #3120699) | Cod sursa (job #510242) | Cod sursa (job #318299) | Cod sursa (job #2480308)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int DIM = 307;
int cap[DIM][DIM];
int in[DIM];
int out[DIM];
int dist[DIM];
pair <int, int> v[DIM];
vector <pair <int, int> > res;
vector <int> retea[DIM];
int from[DIM];
int S, D;
int n;
bitset <DIM> vis;
bool bfs()
{
vis.reset();
queue <int> q;
vis[S] = true;
q.push(S);
while(!q.empty())
{
int nod = q.front();
q.pop();
for(auto i : retea[nod])
if(vis[i] == false && cap[nod][i] > 0)
{
vis[i] = true;
from[i] = nod;
if(i != D)
{
q.push(i);
}
}
}
if(vis[D] == true)
{
return true;
}
return false;
}
void muchie(int x, int y, int val)
{
retea[x].push_back(y);
retea[y].push_back(x);
cap[x][y] += val;
}
main()
{
fin >> n;
for(int i = 1; i <= n; i++)
{
fin >> v[i].first;
fin >> v[i].second;
}
S = 0;
D = 2 * n + 1;
for(int i = 1; i <= n; i++)
{
if(v[i].first)
muchie(S, i, v[i].first);
if(v[i].first)
for(int j = 1; j <= n; j++)
if(i != j)
{
if(v[j].second)
muchie(i, j + n, 1);
}
if(v[i].second)
muchie(i + n, D, v[i].second);
}
while(bfs())
{
for(int i = D; i != S; i = from[i])
{
cap[from[i]][i]--;
cap[i][from[i]]++;
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(cap[i + n][j])
res.push_back({j, i});
fout << res.size() << '\n';
for(auto i : res)
{
fout << i.first << ' ' << i.second << '\n';
}
}