Pagini recente » Cod sursa (job #1478942) | Cod sursa (job #3265128) | Cod sursa (job #1576865) | Cod sursa (job #1395689) | Cod sursa (job #585158)
Cod sursa(job #585158)
#include<fstream>
#include<vector>
#include<queue>
#include<iostream>
#include<bitset>
#define Nmax 301
#define INF 0x3f3f3f3f
using namespace std;
int N,S,D,C[Nmax][Nmax],F[Nmax][Nmax],T[Nmax];
vector<int> G[Nmax];
queue<int> Q;
bitset<Nmax> viz;
void read()
{
ifstream f("harta.in");
f>>N;
int i,a,b;
D = 300;
for(i=1;i<=N;++i)
{
f>>a>>b;
G[0].push_back(i);
C[0][i] = a;
G[i+N].push_back(D);
C[i+N][D] = b;
G[D].push_back(i+N);
}
f.close();
int j;
for(i=1;i<=N;++i)
for(j=1;j<=N;++j)
if(i!=j && C[0][i] && C[j+N][D])
{
G[i].push_back(j+N);
G[j+N].push_back(i);
C[i][j+N] = 1;
}
}
int bf()
{
viz.reset();
Q.push(S);
int nod;
while(!Q.empty())
{
nod = Q.front();
Q.pop();
if(nod == D)continue;
for(vector<int>::iterator it = G[nod].begin();it!=G[nod].end();++it)
if(!viz[*it] && C[nod][*it] > F[nod][*it])
{
T[*it] = nod;
viz[*it] = 1;
Q.push(*it);
}
}
return viz[D];
}
int main()
{
read();
int i,r,x=0;
while(bf())
{
for(vector<int>::iterator it = G[D].begin();it!=G[D].end();++it)
if(T[*it] && C[*it][D] > F[*it][D])
{
T[D] = *it;
i = D;
r = INF;
while(i!=S)
{
r = min(r,C[T[i]][i] - F[T[i]][i]);
i = T[i];
}
if(r==0)continue;
i = D;
while(i!=S)
{
F[T[i]][i] += r;
F[i][T[i]] -= r;
i = T[i];
}
}
++x;
if(x==2)
x=2;
}
ofstream g("harta.out");
int j,sol[2][Nmax],nr=0;
for(i=1;i<=N;++i)
for(j=1;j<=N;++j)
if(F[i][j+N]>0)
{
sol[0][++nr] = i;
sol[1][nr] = j;
}
g<<nr<<"\n";
for(i=1;i<=nr;++i)
g<<sol[0][i]<<" "<<sol[1][i]<<"\n";
g.close();
return 0;
}