Cod sursa(job #1444559)

Utilizator ion824Ion Ureche ion824 Data 29 mai 2015 22:06:46
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 1.84 kb
#include<fstream>
#include<cstring>
#include<algorithm>
#include<vector>
#define pb push_back
using namespace std;
const int NM = 203;
const int INF = 0x3f3f3f3f;
 
vector<int> V[NM];
vector<int>::iterator it;
bool viz[NM];
int F[NM][NM];
int Q[NM],from[NM];
int ansX[NM],ansY[NM],K;
int N,Dest,maxflow;
 
void Update(){
     int vf=Dest,mn=INF;
      
     while(from[vf]!=-1)
     {
       mn=min(mn,F[from[vf]][vf]);
       vf=from[vf];
     }
     vf=Dest;
      
     if(mn==0 || mn==INF) return;
      
     while(from[vf]!=-1)
     {
       F[from[vf]][vf]-=mn;      
       F[vf][from[vf]]+=mn; 
       vf=from[vf];
     }
     maxflow+=mn;    
}
 
bool bfs(){
     int i,nod;
     bool ok=0;
      
     memset(viz,0,sizeof(viz));
     Q[0]=1; Q[1]=0;
     viz[0]=1; 
     from[0]=-1;
      
     for(i=1;i<=Q[0];++i)
     {
       nod=Q[i];
       for(it=V[nod].begin();it!=V[nod].end();++it)
         if(!viz[*it] && F[nod][*it]>0)
         {
            if(*it != Dest) Q[++Q[0]] = (*it);
            viz[*it]=1;
            from[*it]=nod;
         }                
        if(viz[Dest]){ ok=1; Update(); viz[Dest]=0; } 
     }
      
    return ok; 
}
 
 
 
int main(){
    ifstream cin("harta.in");
    ofstream cout("harta.out");
    int i,j,x,y;
     
    cin>>N;
    Dest=2*N+1;
    for(i=1;i<=N;++i)
    {
      cin>>x>>y;
      V[0].pb(i);
      F[0][i]=x;
      V[N+i].pb(Dest); 
      F[N+i][Dest]=y;           
    }
     
    for(i=1;i<=N;++i)
      for(j=1;j<=N;++j)
        if(i!=j)
        {
          F[i][N+j]=1;
          V[i].pb(N+j);
          V[N+j].pb(i);
        }
         
    while(bfs()) ;
 
    cout<<maxflow<<'\n';
          
      for(i=1;i<=N;++i)
        for(j=1;j<=N;++j)
          if(F[j+N][i]) cout<<i<<' '<<j<<'\n';
        
 return 0;   
}