Pagini recente » Cod sursa (job #1230210) | Cod sursa (job #3239124) | Cod sursa (job #593843) | Cod sursa (job #113213) | Cod sursa (job #2958091)
#include <iostream>
#include <fstream>
#include <math.h>
#include <queue>
#define MAX 110000
using namespace std;
//Idee: dublez toate nodurile din graf
ifstream in("harta.in");
ofstream out("harta.out");
int n, grInt, grExt; //gradul interior si exterior total
int flux[1000][1000];
vector<int> tata;
int m;
int bfs()
{
queue<int> q;
for(int i=0; i<=2*n+1; i++)
tata[i] = -1; //vectorul de tati se modifica la fiecare parcurgere
q.push(0);
while(!q.empty())
{
int nod = q.front();
q.pop();
for(int i = 1; i<= 2*n+1; i++)
{
if(flux[nod][i] != 0 && tata[i] == -1) //daca am muchie intre nod si i si i nu e vizitat inca
{
tata[i] = nod;
q.push(i);
if(i == 2*n+1) //daca am ajuns la final de lant
{
return 1;
}
}
}
}
return 0;
}
int main()
{
in>>n;
int x, y;
tata.resize(2*n+2);
for(int i=1; i<=n; i++)
{
in>>x>>y;
grInt += x;
grExt += y;
flux[0][i] = x;
flux[i+n][2*n+1] = y;
}
if(grInt != grExt)
{
out<<-1;
return 0;
}
for(int i=1; i<=n; i++)
{
for(int j=n+1; j<=2*n; j++)
{
if(i != j-n) //intre un nod si dublura sa nu am muchie
flux[i][j] = 1; //intre oricare nod si alta dublura am muchie
}
}
while(bfs() != 0)
{
int nod = 2*n+1;
while(nod != 0) //revizuiesc gradele pe graful invers
{
int t = tata[nod];
flux[t][nod]--;
flux[nod][t]++;
nod = t;
}
}
if((grInt+grExt)/2 < grInt)
{
out<<-1;
return 0;
}
out<<(grInt+grExt)/2<<"\n"; //nr total de grade e calculat pt graful dublat
for(int i=1; i<=n; ++i)
for(int j=1+n; j<=2*n; j++)
if(flux[j][i] != 0)
out<<i<<" "<<j-n<<"\n";
return 0;
}