Cod sursa(job #3187271)

Utilizator fabian_anghelFabian Anghel fabian_anghel Data 28 decembrie 2023 12:38:20
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int N,M,k,x,parent[202],dst,cap[202][202],flow[202][202],in,out;
bool visited[202];
ifstream f ("harta.in");
ofstream g ("harta.out");
void bfs()
{
    for(int i=1;i<=2*N+1;i++)
    {
        parent[i]=-1; //indicele copilului
        visited[i]=false;
    }
    queue <int> q;
    q.push(0);
    visited[0]=true;
    parent[0]=-1;
    while(!q.empty())
    {
        int k=q.front();
        q.pop();
        if(k!=dst)
        {
            if(k>=1 && k<=N)
            {
                for(int i=N+1;i<=2*N;i++)
                    if(!visited[i] && cap[k][i]!=flow[k][i])
                    {
                        visited[i]=true;
                        parent[i]=k;
                        q.push(i);
                    }
            }
            else
            {
                for(int i=1;i<=N;i++)
                    if(!visited[i] && cap[k][i]!=flow[k][i])
                    {
                        visited[i]=true;
                        parent[i]=k;
                        q.push(i);
                    }
                if(k!=0 && !visited[dst] && cap[k][dst]!=flow[k][dst])
                {
                    visited[dst]=true;
                    parent[dst]=k;
                    q.push(dst);
                }
            }
        }
    }
}
int ford()
{
    int maxflow=0;
    bfs();
    while(visited[dst])
    {
        for(int i=N+1;i<=2*N;i++)
        {
            if(visited[i] && cap[i][dst]!=flow[i][dst])
            {
                parent[dst]=i;
                int minflow=100000,poz=dst;
                while(poz)
                {
                    minflow=min(minflow,cap[parent[poz]][poz]-flow[parent[poz]][poz]);
                    poz=parent[poz];
                }
                if(minflow!=0)
                {
                    maxflow+=minflow;
                    poz=dst;
                    while(poz)
                    {
                        flow[parent[poz]][poz]+=minflow;
                        flow[poz][parent[poz]]-=minflow;
                        poz=parent[poz];
                    }
                }
            }
        }
        bfs();
    }
    return maxflow;
}
int main()
{
    f>>N;
    dst=2*N+1;
    for(int i=1;i<=N;i++)
    {
        f>>out>>in;
        M+=out;
        cap[0][i]=out;
        cap[i+N][dst]=in;
    }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            if(j!=i)
                cap[i][j+N]=1;
    g<<ford()<<'\n';
    for(int i=1;i<=N;i++)
        for(int j=N+1;j<=2*N;j++)
            if(flow[i][j])
                g<<i<<' '<<j-N<<'\n';
    f.close();
    g.close();
    return 0;
}