Cod sursa(job #3190075)

Utilizator fresh.mintyAlexandru Andrei fresh.minty Data 6 ianuarie 2024 22:06:36
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <limits>
#include <climits>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
#define intmax INT_MAX
#define N 1002
int capacitate[N][N];
int flux[N][N];
vector<int> graf[N];
vector<int> tati;
int bfs(int s, int t)
{
    deque<int> deq;
    vector<int> viz(t+1,0);
    tati.assign(t+1,0);

    deq.push_back(s);
    viz[s]=1;

    while (deq.size()>0)
    {
        int nod=deq.front();
        deq.pop_front();

        if (nod==t)
            break;

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

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

    if (tati[t]!=0)
        return 1;
    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=intmax;
        int i=d;

        while (i!=0)
        {
            if(capacitate[tati[i]][i]-flux[tati[i]][i]<mini)
                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;
}