Pagini recente » Cod sursa (job #1636332) | Cod sursa (job #2218232) | Cod sursa (job #1118371) | Cod sursa (job #913525) | Cod sursa (job #1690487)
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector <int> G[205];
int Source,Sink,C[205][205],TT[205],F[205][205],N;
queue <int> Q;
bool Use[205];
void Read()
{
f>>N;
Sink=2*N+1;
for(int i=1;i<=N;i++)
{
int x,y;
f>>x>>y;
C[Source][i]=x;
C[i+N][Sink]=y;
}
for(int i=1;i<=N;i++)
{
G[Source].push_back(i);
G[i].push_back(Source);
G[i+N].push_back(Sink);
G[Sink].push_back(i+N);
}
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
if(i!=j)
{
C[i][j+N]=1;
G[i].push_back(j+N);
G[j+N].push_back(i);
}
}
int BFS()
{
memset(Use,0,sizeof(Use));
Q.push(Source); Use[Source] = 1;
while(!Q.empty())
{
int Node = Q. front(); Q. pop();
if(Node == N) continue;
for(unsigned int i = 0; i < G[Node].size(); ++i)
{
int Neighbour = G[Node][i];
if(!Use[Neighbour] && C[Node][Neighbour]-F[Node][Neighbour]>0)
{
TT[Neighbour] = Node;
Q.push(Neighbour);
Use[Neighbour] = 1;
}
}
}
return Use[N];
}
void Solve()
{
int number=N;
N=Sink;
while(BFS())
{
for(unsigned int k = 0; k<G[N].size(); ++k)
{
int Vecin = G[N][k];
if(!Use[Vecin] || C[Vecin][N]-F[Vecin][N] == 0) continue;
TT[N] = Vecin;
int Fmin = 120000;
for(int i = N ; i != 0 ; i = TT[i])
Fmin = min(Fmin,C[TT[i]][i]-F[TT[i]][i]);
for(int i = N ; i != 0 ; i = TT[i])
{
F[TT[i]][i] += Fmin;
F[i][TT[i]] -= Fmin;
}
}
}
int ans=0;
N=number;
for(int i=1;i<=N;i++)
for(int j=N+1;j<=2*N;j++)
if(F[i][j]!=0)
++ans;
g<<ans<<"\n";
for(int i=1;i<=N;i++)
for(int j=N+1;j<=2*N;j++)
if(F[i][j]!=0)
g<<i<<" "<<j-N<<"\n";
}
int main()
{
Read();
Solve();
return 0;
}