Pagini recente » Cod sursa (job #2889637) | Cod sursa (job #2468945) | Cod sursa (job #1504703) | Cod sursa (job #2477867) | Cod sursa (job #496971)
Cod sursa(job #496971)
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int INF = 1000000000;
const int NMAX = 105;
int N, MCH;
int coada[NMAX * NMAX], tata[NMAX * NMAX];
vector<int> V[2 * NMAX];
int C[2 * NMAX][2 * NMAX];
int F[2 * NMAX][2 * NMAX];
pair<int, int> grad[NMAX];
pair<int, int> M[NMAX * NMAX];
void citire()
{
scanf("%d",&N);
for(int i = 1; i <= N ; i++)
scanf("%d %d", &grad[i].first, &grad[i].second);
}
void face_muchii()
{
for(int i = 1 ; i <= N ; i++)
{
V[0].push_back(i);
V[i].push_back(0);
C[0][i] = grad[i].first;
}
for(int i = 1 ; i <= N ; i ++)
for(int j = N + 1 ; j <= 2 * N ; j++)
if(i + N != j)
{
V[i].push_back(j);
V[j].push_back(i);
C[i][j] = 1;
}
for(int i = N + 1 ; i <= 2 * N ; i++)
{
V[2 * N + 1].push_back(i);
V[i].push_back(2 * N + 1);
C[i][2 * N + 1] = grad[i - N].second;
}
}
bool BFS()
{
bool viz[2 * NMAX] = {0};
fill(coada, coada + 2 * NMAX, 0);
coada[++coada[0]] = 0;
for(int i = 1 ; i <= coada[0] ; i++)
{
for(vector<int> :: iterator it = V[coada[i]].begin() ; it != V[coada[i]].end() ; it++)
if(F[coada[i]][*it] < C[coada[i]][*it] && !viz[*it])
{
tata[*it] = coada[i];
if(*it == 2 * N + 1)
return 1;
coada[++coada[0]] = *it;
viz[*it] = 1;
}
}
return 0;
}
void flux()
{
while(BFS())
{
int min_flow = INF;
for(int i = 2 * N + 1 ; i ; i = tata[i])
min_flow = min(min_flow, C[tata[i]][i] - F[tata[i]][i]);
for(int i = 2 * N + 1 ; i ; i = tata[i])
{
F[tata[i]][i] += min_flow;
F[i][tata[i]] -= min_flow;
}
}
}
void numara_muchii()
{
for(int i = 1 ; i <= N ; i ++)
for(int j = N + 1 ; j <= 2 * N ; j++)
if(F[i][j] == 1)
{
M[++MCH].first = i;
M[MCH].second = j - N;
}
}
void scrie()
{
printf("%d\n", MCH);
for(int i = 1 ; i <= MCH ; i++)
printf("%d %d\n", M[i].first, M[i].second);
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
citire();
face_muchii();
flux();
numara_muchii();
scrie();
return 0;
}