Cod sursa(job #3190763)

Utilizator FoxBlood001Iulian FoxBlood001 Data 7 ianuarie 2024 23:18:56
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.37 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;
}