Cod sursa(job #2959748)

Utilizator DragosG12Ghinea Dragos DragosG12 Data 2 ianuarie 2023 16:23:45
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.02 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#include<climits>
using namespace std;

int n;
int s,t;

struct muchie{
    int nodDest;
    int capacitate;
    int flux;
    int revers;
    
    muchie(int dest, int cap, int fl, int revers1)
    : nodDest(dest), capacitate(cap), flux(fl), revers(revers1){};
};

bool bfs(int vizitate[], vector<muchie> muchii[]){
    memset(vizitate, 0, sizeof(int)*(n*2+2));

    queue<int> q;
    
    for(muchie& m : muchii[s])
        if(m.flux != m.capacitate){
            vizitate[m.nodDest] = true;
            q.push(m.nodDest);
        }
    
    while(!q.empty()){
        int nod = q.front(); q.pop();
        if(nod==t)
            return true;
        for(muchie& m : muchii[nod]){
            if(!vizitate[m.nodDest] && m.flux < m.capacitate){
                vizitate[m.nodDest] = true;
                q.push(m.nodDest);
            }
        }
    }
    
    return false;
}

int trimite(int start, int flux, int vizitate[], vector<muchie> muchii[]){
    if(start==t)
        return flux;
        
    vizitate[start]=1;
    
    for(muchie& m : muchii[start]){
        if(!vizitate[m.nodDest] && m.flux < m.capacitate){
            int fluxC;
            if(flux < m.capacitate - m.flux)
                fluxC = flux;
            else
                fluxC = m.capacitate - m.flux;
            
            int fluxT = trimite(m.nodDest, fluxC, vizitate, muchii);
            if(fluxT > 0){
                m.flux += fluxT;
                if(m.revers!=-1){
                    muchii[m.nodDest][m.revers].flux -= fluxT;
                }
                return fluxT;
            }
        }
    }
    
    return 0;
}

int **indexMuchii;

int main(){
    ifstream fin("harta.in");
    ofstream fout("harta.out");
    fin>>n;
    
    s=0, t=n*2+1;
    
    vector<muchie> muchii[n*2+2];
    int **indexMuchii=new int*[n+1];
    for(int i=1;i<=n;i++)
        indexMuchii[i]=new int[n+1];
        
    int x,y;
    for(int i=1;i<=n;i++){
        fin>>x>>y;
        muchii[s].push_back(muchie(i,x,0,-1));
        muchii[i+n].push_back(muchie(t, y, 0, -1));
        
        for(int j=1;j<=n;j++){
            if(i==j){
                continue;
            }
            int lastPozi = muchii[i].size();
            int lastPozj = muchii[j+n].size();
            indexMuchii[i][j]=lastPozi;
            muchii[i].push_back(muchie(j+n,1,0,lastPozj));
            muchii[j+n].push_back(muchie(i,0,0,lastPozi));
        }
    }
    
    
    int vizitate[n*2+2];
    int vizitate2[n*2+2];

    while(bfs(vizitate, muchii)){
        memset(vizitate2, 0, sizeof(int)*(n*2+2));
        while(trimite(s, INT_MAX, vizitate2, muchii));
    }
    
    vector<pair<int,int>> rez;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(i==j)
                continue;
            if(muchii[i][indexMuchii[i][j]].flux==1)
                rez.push_back({i,j});
        }

    fout<<rez.size()<<"\n";
    for(pair<int,int>& m : rez)
        fout<<m.first<<" "<<m.second<<"\n";
    return 0;
}