Pagini recente » Cod sursa (job #1689598) | Cod sursa (job #2516319) | Cod sursa (job #1202388) | Cod sursa (job #1019363) | Cod sursa (job #1051862)
#include <fstream>
#include <iostream>
#include <bitset>
#include <queue>
using namespace std;
const int NMax = 204;
int C[NMax][NMax];
int F[NMax][NMax];
bitset < NMax > viz;
int degreein[NMax],degreeout[NMax];
int n,source, destination , Father[NMax];
inline void Read()
{
ifstream f("harta.in");
f >> n ;
for(int i = 1 ;i <= n; ++i)
f >> degreeout[i] >> degreein[i] ;
f.close();
}
inline void BuildGraph()
{
int i ,j ;
source = 0;
destination = 2*n+1;
for(i = 1;i <= n; ++i)
{
C[source][i] = degreeout[i];
C[i+n][destination] = degreein[i];
for(j = n+1;j < destination; ++j)
if(i != j-n)
C[i][j] = 1;
}
}
inline bool BFS()
{
viz = 0;
queue < int >Q;
int node, i;
viz[source] = 1;
for(Q.push(source); !Q.empty(); Q.pop())
{
node = Q.front();
if(node==destination)
continue;
for(i = 1;i <= destination; ++i)
if(!viz[i] && F[node][i] < C[node][i])
{
viz[i] = 1;
Q.push(i);
Father[i] = node;
}
}
return viz[destination];
}
inline void MaxFlow()
{
int node;
while(BFS())
{
for(node = destination ; node != source ;node = Father[node])
{
F[Father[node]][node]++;
F[node][Father[node]]--;
}
}
}
inline void Write()
{
vector < pair < int , int > > sol;
int i,j;
for(i = 1;i <= n;++i)
for(j = n+1;j < destination; ++j)
if(F[i][j] ==1)
sol.push_back(make_pair(i,j-n));
ofstream g("harta.out");
g<< ( j = sol.size())<<"\n";
for(i = 0 ; i < j ; ++i)
g<<sol[i].first<<" "<<sol[i].second<<"\n";
g.close();
}
int main()
{
Read();
BuildGraph();
MaxFlow();
Write();
return 0;
}