Cod sursa(job #1228602)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 14 septembrie 2014 18:24:36
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.28 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fi("harta.in");
ofstream fo("harta.out");

const int max_n = 105;

vector <int> a[2*max_n+1];
queue <int> q;
int Capacity[2*max_n+1][2*max_n+1],Flow[2*max_n+1][2*max_n+1],Max_Flow;
int start_node,end_node,out_degree,in_degree,P[2*max_n+1];
bool viz[2*max_n+1];
int i,j,n;

bool augmenting_path(const int &start_node, const int &end_node){
     for(int i=0;i<=2*n+1;i++) viz[i]=0;
     
     q.push(start_node);
     viz[start_node]=1;
     P[start_node]=start_node;
     
     while(q.size())
          {
           int x=q.front();
           q.pop();
           if(x==end_node) continue;
           for(int j=0;j<(int)a[x].size();j++)
              {
               int y=a[x][j];
               if(!viz[y] && Capacity[x][y]>Flow[x][y]){
                                                        q.push(y);
                                                        viz[y]=1;
                                                        P[y]=x;
                                                       }    
              }
          }
          
     return viz[end_node];
}

int find_path_capacity_and_update(const int &start_node, const int &second_last, const int &end_node){
    int path_capacity=Capacity[second_last][end_node]-Flow[second_last][end_node];
    int y;
    
    P[end_node]=second_last;
    
    //find path_capacity
    y=end_node;
    while(y!=P[y]){
                   if(path_capacity>Capacity[P[y]][y]-Flow[P[y]][y])
                      path_capacity=Capacity[P[y]][y]-Flow[P[y]][y];
                   y=P[y];
                  }
                  
    //update
    y=end_node;
    while(y!=P[y]){
                   Flow[P[y]][y]+=path_capacity;
                   Flow[y][P[y]]-=path_capacity;
                   y=P[y]; 
                  }
    
    return path_capacity;
}

int main(){
    fi>>n; start_node=0; end_node=2*n+1;
    for(i=1;i<=n;i++){
                      fi>>out_degree>>in_degree;
                      
                      a[start_node].push_back(i);
                      a[i].push_back(start_node);
                      Capacity[start_node][i]=out_degree;
                      
                      a[i+n].push_back(end_node);
                      a[end_node].push_back(i+n);
                      Capacity[i+n][end_node]=in_degree;
                     }
    
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        if(i!=j){
                 a[j+n].push_back(i);
                 a[i].push_back(j+n);
                 Capacity[i][j+n]=1;
                } 
    
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++) Flow[i][j]=0;
    Max_Flow=0;
    
    for(;augmenting_path(start_node,end_node);)
      for(int j=0;j<(int)a[end_node].size();j++) 
         {
          int y=a[end_node][j];
          if(viz[y] && Capacity[y][end_node]>Flow[y][end_node])
            {
             int path_capacity=find_path_capacity_and_update(start_node,y,end_node);
             Max_Flow+=path_capacity;
            }                  
         }
    
    fo<<Max_Flow<<"\n";
    for(i=1;i<=n;i++)
      for(j=n;j<=2*n;j++)
        if(Flow[i][j]>0) fo<<i<<" "<<j-n<<'\n';
        
    fi.close();
    fo.close();
    return 0;
}