Cod sursa(job #475771)

Utilizator APOCALYPTODragos APOCALYPTO Data 8 august 2010 14:26:28
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<cstring>
#include<queue>
#define Nmax 105
#define pb push_back
#define oo 0x3f3f3f3f
ofstream fout("harta.out");
int in[Nmax],out[Nmax];
vector<int> G[2*Nmax+2];
int C[2*Nmax+2][2*Nmax+2],F[2*Nmax+2][2*Nmax+2],N,M,ante[2*Nmax+2];
int viz[2*Nmax+2];
int BFS()
{queue<int> q;
int u;
vector<int>::iterator it;

    memset(viz,0,sizeof(viz));
    q.push(0);
    viz[0]=1;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        for(it=G[u].begin();it!=G[u].end();it++)
        {
            if(viz[*it]==0)
             if(F[u][*it]<C[u][*it])
             {//cout<<0;
                 viz[*it]=1;
                 ante[*it]=u;
                 q.push(*it);
                 if(*it==2*N+1)
                 return 1;

             }
        }
    }
    return 0;




}
void solve()
{int i,j,flow,fmin;
    for(i=1;i<=N;i++)
    {C[0][i]=out[i];
    G[0].pb(i);
    G[i].pb(0);

    for( j=1;j<=N;j++)
       if(i!=j)
       { C[i][N+j]=1;
       G[i].pb(N+j);
       G[N+j].pb(i);

    }
}
    //cout<<0;
    for(i=1;i<=N;i++)
    {C[N+i][N+N+1]=in[i];
    G[N+i].pb(N+N+1);
    G[N+1+N].pb(N+i);
    }
    for(flow=0;BFS(); flow+=fmin)
    {   //cout<<1;
        fmin=oo;
        for(i=2*N+1;i>0;i=ante[i])
        {
        fmin=min(fmin,C[ante[i]][i]-F[ante[i]][i]);
        //cout<<i;
        }
        for(i=2*N+1;i>0;i=ante[i])
        {
            F[ante[i]][i]+=fmin;
            F[i][ante[i]]-=fmin;

        }
    }



    fout<<flow<<"\n";
    for(i=1;i<=N;i++)
      for(j=N+1;j<=2*N;j++)
       if(F[i][j]==1)
        fout<<i<<" "<<j-4<<"\n";



}
void cit()
{int x,y,i;
    ifstream fin("harta.in");
    fin>>N;
    for(i=1;i<=N;i++)
    {
        fin>>x>>y;
        in[i]=y;//<==e bine asa stay cool
        out[i]=x;
    }
    fin.close();
}

int main()
{
  cit();

  solve();
  fout.close();
  return 0;
}