Cod sursa(job #2960022)

Utilizator RosianuRobertRosianu Robert RosianuRobert Data 3 ianuarie 2023 14:13:27
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector<int> adj[1030];
int MaxFLOW,flow,fluxmin,fluxmax;
int i,j,k,n,m,C[1030][1030],x,y,z,fth[1030],nod,F[6001][6001],e,source,last_node,viz[6001];
int bfs()
{
    int top,next;
    for(int i=1;i<=2*n+2;i++)
    {
        viz[i] = 0;
    }
    queue<int>q;
    q.push(0);
    //viz[0] = 1;
    while(q.empty() == false)
    {
        top = q.front();
        q.pop();
        viz[top] = 1;
        if(top == n+n+1)
            break;
        for(int i=0; i<adj[top].size(); i++)
        {
            next = adj[top][i];
            if(viz[next] == 0 && F[top][next] != C[top][next])
            {
                q.push(next);
                viz[next]=1;
                fth[next] = top;
            }
        }
    }
    return viz[n];
}
int main()
{
    f>>n;
    last_node = 2*n+1;
    source = 0;
    for(i=1;i<=n;i++)
    {
        f>>x>>y;
        adj[source].push_back(i);
        adj[i].push_back(source);
        adj[last_node].push_back(n+i);
        adj[n+i].push_back(last_node);
        C[0][i] = x;
        C[i+n][2*n+1] = y;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1+n;j<=2*n;j++)
        {
            if(i!=j-n)
            {
                C[i][j] = 1;
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    for(MaxFLOW = 0; bfs();)
    {
        for(i=0; i<adj[last_node].size(); i++)
        {
            fluxmin = 10e7;
            nod = adj[last_node][i];
            if(!viz[nod] || F[nod][last_node] == C[nod][last_node])
                continue;
            fth[last_node] = nod;
            for(nod = last_node; nod != source ; nod = fth[nod])
            {
                fluxmin = min(fluxmin,C[fth[nod]][nod] - F[fth[nod]][nod]);
            }
            if(fluxmin == 0)
                continue;
            for (nod = last_node; nod != source ; nod = fth[nod])
            {
                F[fth[nod]][nod] += fluxmin;
                F[nod][fth[nod]] -= fluxmin;
            }
            MaxFLOW += fluxmin;
        }
        // MaxFLOW += fluxmin;
    }
    g<<MaxFLOW<<'\n';
    for(i=1;i<=n;++i)
    {
        for(j=0;j<adj[i].size();j++)
        {
            if(adj[i][j] && F[i][adj[i][j]])
                g<<i<<" "<<adj[i][j]-n<<'\n';
        }
    }
    return 0;
}