Cod sursa(job #2966055)

Utilizator cristina.damov@s.unibuc.roCristina [email protected] Data 16 ianuarie 2023 18:23:27
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> LA;
vector<int> F;
int cap[201][201];
int n,s,t;

bool bfs()
{
    vector<bool> viz(2*n+1);
    queue<int> q;
    q.push(s);
    viz[s] = true;
    F[s] = -1;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(auto v: LA[u]) {
            if(viz[v]==false && cap[u][v]!=0) {
                F[v] = u;
                if(v == t)
                    return true;
                viz[v] = true;
                q.push(v);
            }
        }
    }
    return false;
}

int ekarp()
{
    long max_flow = 0;
    while(bfs()==true) {
        int u, v, path_flow = INT_MAX;
        v=t;
        while(v!=s) {
            u = F[v];
            if(cap[u][v] < path_flow)
                path_flow = cap[u][v];
            v = F[v];
        }
        v=t;
        while(v!=s) {
            u = F[v];
            cap[u][v] -= path_flow;
            cap[v][u] += path_flow;
            v = F[v];
        }
        max_flow += path_flow;
    }
    return max_flow;
}


int main()
{
    ifstream f("harta.in");
    ofstream g("harta.out");
    f>>n;
    int a,b,i,j;
    LA.resize(201);
    F.resize(2*n+1);
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++) {
            if(i!=j) {
                LA[i].push_back(j+n);
                LA[j+n].push_back(i);
                cap[i][j+n]=1;
            }
        }
    s=0;
    t=2*n+1;
    for(i=1; i<=n; i++) {
        f>>a>>b;
        LA[s].push_back(i);
        LA[i].push_back(s);
        cap[s][i]=a;
        LA[i+n].push_back(t);
        LA[t].push_back(i+n);
        cap[i+n][t]=b;
    }

    g<<ekarp()<<"\n";
    for(i=1; i<=n; i++)
        for(j=n+1; j<=2*n; j++) {
            if(cap[j][i]==1)
                g<<i<<" "<<j-n<<"\n";
        }

    f.close(); g.close();
    return 0;
}