Pagini recente » Cod sursa (job #538270) | Cod sursa (job #3249296) | Sopterean Adrian | Cod sursa (job #3186077) | Cod sursa (job #830600)
Cod sursa(job #830600)
#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
#define DIM 5000
#define FOR for(it=v[nod].begin();it!=v[nod].end();++it)
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,nr=0;
int i,j,r;
int a,b;
int A[DIM][DIM];
int mat[DIM][DIM];
int v2[DIM];
int sol[2][DIM];
vector<int> v[DIM];
queue<int> q;
vector<int>::iterator it;
bitset<DIM> viz;
int s,d;
inline int bfs()
{
viz.reset();
q.push(s);
int nod;
while(!q.empty())
{
nod=q.front();
q.pop();
FOR
if(!viz[*it]&&A[nod][*it]>mat[nod][*it])
{
v2[*it]=nod;
viz[*it]=1;
q.push(*it);
}
}
return viz[d];
}
int main()
{
f>>n;
d=300;
for(i=1;i<=n;++i)
{
f>>a>>b;
v[0].push_back(i);
A[0][i]=a;
v[i+n].push_back(d);
A[i+n][d]=b;
v[d].push_back(i+n);
}
int j;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
if(i!=j&&A[0][i]&&A[j+n][d])
{
v[i].push_back(j+n);
v[j+n].push_back(i);
A[i][j+n] = 1;
}
do
{
for(it=v[d].begin();it!=v[d].end();++it)
if(viz[*it]&&A[*it][d]>mat[*it][d])
{
v2[d]=*it;
i=d;
r=INF;
while(i!=s)
{
r=min(r,A[v2[i]][i]-mat[v2[i]][i]);
i=v2[i];
}
i=d;
while(i!=s)
{
mat[v2[i]][i]+=r;
mat[i][v2[i]]-=r;
i=v2[i];
}
}
}while(bfs());
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
if(mat[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";
return 0;
}