Cod sursa(job #2962282)

Utilizator denisaaabBucur Denisa Andreea denisaaab Data 8 ianuarie 2023 09:01:27
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");

int n, m, e, mxflow;
int viz[205];
int tata[205];
int flux[205][205], c[205][205];
vector <int> adjlist[205];
int grin[205],grout[205];
bool modifiedBfs(int finish)
{

    for(int i = 0; i <= 2*n+1; i++)
        viz[i]=0,tata[i]=0;

    int nod=0;
    queue <int> Q;
    Q.push(nod);
    viz[nod] = 1;
    tata[0] = -1;
    while(!Q.empty())
    {
        nod = Q.front();
        Q.pop();
        for(int i=0; i<adjlist[nod].size(); i++)
        {
            int vecin=adjlist[nod][i];
            if(viz[vecin]!=1 && c[nod][vecin] - flux[nod][vecin] > 0)
            {
                viz[vecin] = 1;
                tata[vecin] = nod;
                Q.push(vecin);
            }
        }
    }
    if(!tata[finish])
        return false;
    int start=0;
    for(int i=0; i<adjlist[finish].size(); i++)
    {
        int vecin=adjlist[finish][i];
        if(c[vecin][finish] - flux[vecin][finish] > 0)
        {

            int maxFlowLant = c[vecin][finish] - flux[vecin][finish];
            for(int j = vecin; j != start; j = tata[j])
            {
                maxFlowLant = min(maxFlowLant, c[tata[j]][j] - flux[tata[j]][j]);

            }
            flux[vecin][finish] += maxFlowLant;
            flux[finish][vecin] -= maxFlowLant;
            for(int j = vecin; j != start; j = tata[j])
            {
                flux[tata[j]][j] += maxFlowLant;
                flux[j][tata[j]] -= maxFlowLant;
            }
            mxflow += maxFlowLant;
        }
    }
    return true;
}
int main()
{
    f>>n;
    int start=0,  finish=n*2+1;
    int x, y;
    for(int i = 1; i <= n; i++)
    {
        f>>x>>y;
        grout[i]=x;
        grin[i]=y;
        c[start][i]=x;
        adjlist[start].push_back(i);
        adjlist[i].push_back(start);

        c[i+n][finish]=y;
        adjlist[finish].push_back(i+n);
        adjlist[i+n].push_back(finish);
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i!=j)
            {
                adjlist[i].push_back(j+n);
                adjlist[j+n].push_back(i);
                c[i][j+n]=1;
            }
    while(modifiedBfs(finish)==true)
    {
        modifiedBfs(finish);
    }
    g<<mxflow<<endl;
    for(int i = 1; i <= n; i++)
    {
        for(int j = n+1; j <= 2*n; j++)
        {
            if(flux[i][j] == c[i][j] && flux[i][j] == 1)
            {
                g<<i<< " "<<j - n<< "\n";
            }
        }
    }
    return 0;
}