Cod sursa(job #3181416)

Utilizator infomatic2Liviu Firca infomatic2 Data 6 decembrie 2023 23:42:24
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 2.31 kb
#include<fstream>
#include<vector>
#include<queue>

using namespace std;
constexpr int nmax=300;
int fluxul[nmax][nmax];
int capacitati[nmax][nmax];
vector<int> graf[nmax];
int tata[nmax];
int nodePathCapacity[nmax];
ifstream cin("harta.in");
ofstream cout("harta.out");

void printMatrice(int* matrice,int size){
    cout<<"============================================\n";
    for(int i=0;i<size;i++){
        for(int j=0;j<size;j++){
            cout<<matrice[i*size+j]<<" ";

        }
        cout<<"\n";
    }
}

int bfs(int s,int t,int size){
    nodePathCapacity[s]=__INT_MAX__;
    for(int i=0;i<=size;i++){
        tata[i]=-1;
    }
    tata[s]=-2;
    queue<int> q;
    q.push(s);
    
    while (!q.empty())
    {
        int current=q.front();
        q.pop();
        for(int next:graf[current]){
            if(tata[next]==-1&&capacitati[current][next]>fluxul[current][next]){
                tata[next]=current;
                nodePathCapacity[next]=min(nodePathCapacity[current],capacitati[current][next]-fluxul[current][next]);
                if(next==t) return nodePathCapacity[next];
                q.push(next);
            }
        }
    }
    return 0;
    
}

int main(){

int n;
cin>>n;
int muchii_totale=0;// imi trebuie cand afisez
int s=0;
int t=n+n+1;


for(int i=1;i<=n;i++){//pt fiecare oras
    int x,y;
    cin>>x>>y;
    muchii_totale+=x;
    for(int j=1;j<i;j++){//leg orasul i cu toate doar nu el
        graf[i].push_back(j+n);
        graf[j+n].push_back(i);
        capacitati[i][j+n]=1;
    }
    for(int j=i+1;j<=n;j++){//la fel
        graf[i].push_back(j+n);
        graf[j+n].push_back(i);
        capacitati[i][j+n]=1;
    }
    graf[s].push_back(i);
    graf[i].push_back(s);
    capacitati[s][i]=x;

    graf[i+n].push_back(t);
    graf[t].push_back(i+n);
    capacitati[i+n][t]=y;
}



int flow_max=0;
while (1)
{
    int flow=bfs(s,t,t);
    //printMatrice(&fluxul[0][0],nmax);
    if(flow==0) break;
    flow_max+=flow;
    int CurrentNode=t;
    while (CurrentNode!=s)
    {
        int prev=tata[CurrentNode];
        fluxul[prev][CurrentNode]+=flow;
        fluxul[CurrentNode][prev]-=flow;
        CurrentNode=prev;
    }
    
    
}
cout<<muchii_totale<<'\n';
for(int i=1;i<=n;i++){
    for(int j=n+1;j<t;j++){
        if(fluxul[i][j]){
            cout<<i<<" "<<j-n<<"\n";
        }
    }
}

return 0;
}