Cod sursa(job #3190067)

Utilizator fresh.mintyAlexandru Andrei fresh.minty Data 6 ianuarie 2024 21:49:32
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <limits>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");

int capacitate[101][101];
int flux[101][101];
vector<int> graf[101];
vector<int> tati;
int bfs(int s, int d)
{
    queue<int> q;
    vector<int> viz(d+1,0);
    tati.assign(d+1,0);

    q.push(s);
    viz[s]=1;

    while (q.size()>0)
    {
        int nod=q.front();
        q.pop();

        if (nod==d)
            break;

        for (int i=0; i<graf[nod].size(); i++)
        {
            int vecin=graf[nod][i];

            if (!viz[vecin] && (capacitate[nod][vecin]-flux[nod][vecin])>0)
            {
                q.push(vecin);
                tati[vecin]=nod;
                viz[vecin]=1;
            }
        }
    }

    if (tati[d]!=0)
    {
        return 1;
    }
    else
    {
        return 0;
    }

}

int edmond_karp(int s, int d)
{
    int flow=0;
    int mini;

    while (bfs(s,d))///cat timp sunt drumuri de crestere
    {
        mini=INT_MAX;
        int i=d;

        while (i!=0)
        {
            mini = min(mini, capacitate[tati[i]][i]-flux[tati[i]][i]);
            i=tati[i];
        }

        i=d;
        while (i!=0)
        {
            flux[tati[i]][i]+=mini;
            flux[i][tati[i]]-=mini;
            i=tati[i];
        }

        flow+=mini;
    }

    return flow;
}

int main()
{
    int n,s,t;
    s=0;
    f>>n;
    t=2*n+1;
    for (int i=1; i<=n; i++)
    {
        int x,y;
        f>>x>>y;
        int j=n+i;

        graf[s].push_back(i);
        graf[j].push_back(t);
        capacitate[s][i]=x;
        capacitate[j][t]=y;
    }

    for (int i=1; i<=n; i++)
        for (int j=n+1; j<=2*n; j++)
            if ((i%n)!=(j%n))
            {
                graf[i].push_back(j);
                graf[j].push_back(i);
                capacitate[i][j] = 1;
            }



    g<<edmond_karp(s,t)<<endl;

    for (int i=1; i<=n; i++)
        for (int j=n+1; j<=2*n; j++)
        {
            if (flux[i][j]==1)
                g<<i<<" "<<j-n<<endl;
        }

    return 0;
}