Cod sursa(job #2962462)

Utilizator Iordache_AnaIordache Ana-Georgiana Iordache_Ana Data 8 ianuarie 2023 16:56:50
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector<vector<int>> lista;
int cap[205][205],a,b,i,j,u;
vector<int> tata;
int n,s,t;
bool bfs()
{
    vector<bool> viz(2*n+1);
    queue<int> que;
    que.push(s);
    viz[s] = true;
    tata[s] = -1;
    while(!que.empty())
    {
        u = que.front();
        que.pop();
        for(auto v: lista[u])
        {
            if(viz[v]==false && cap[u][v]!=0)
            {
                tata[v] = u;
                if(v == t)
                    return true;
                viz[v] = true;
                que.push(v);
            }
        }
    }
    return false;
}

int EdmondsKarp()
{
    long maxf = 0;
    while(bfs()==true)
    {
        int u, v, drum = INT_MAX;
        v=t;
        while(v != s)
        {
            u = tata[v];
            if(cap[u][v] < drum)
                drum = cap[u][v];
            v = tata[v];
        }
        v=t;
        while(v != s)
        {
            u = tata[v];
            cap[u][v] -= drum;
            cap[v][u] += drum;
            v = tata[v];
        }
        maxf += drum;
    }
    return maxf;
}

int main()
{
    f>>n;
    lista.resize(201);
    tata.resize(2*n+1);
    for( i=1; i<=n; i++)
        for( j=1; j<=n; j++)
        {
            if(i!=j)
            {
                lista[i].push_back(j+n);
                lista[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;
        lista[s].push_back(i);
        lista[i].push_back(s);
        cap[s][i]=a;
        lista[i+n].push_back(t);
        lista[t].push_back(i+n);
        cap[i+n][t]=b;
    }
    g << EdmondsKarp()<<"\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";
        }
    return 0;
}