Cod sursa(job #2680112)

Utilizator bem.andreiIceman bem.andrei Data 2 decembrie 2020 17:43:18
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <bits/stdc++.h>

using namespace std;
ifstream r("harta.in");
ofstream w("harta.out");
int n, parent[203], rez[203][203];
bool viz[203];
vector<int>g[203];
bool bfs()
{
    memset(viz, 0, sizeof(viz));
    queue<int>q;
    q.push(0);
    viz[0]=1;
    parent[0]=-1;
    while(q.size()!=0)
    {
        int a=q.front();
        q.pop();
        if(a!=2*n+1)
        {
            for(auto it: g[a])
            {
                if(viz[it]==0 && rez[a][it]>0)
                {
                    q.push(it);
                    parent[it]=a;
                    viz[it]=true;
                }
            }
        }
    }
    return viz[2*n+1];
}
int flux()
{
    int flow=0;
    while(bfs()!=0)
    {
        for(auto it: g[2*n+1])
        {
            if(rez[it][2*n+1]>0 && viz[it]==1)
            {
                parent[2*n+1]=it;
                int fluxm=1000000000, nod=2*n+1;
                while(nod!=0)
                {
                    fluxm=min(fluxm, rez[parent[nod]][nod]);
                    nod=parent[nod];
                }
                nod=n*2+1;
                while(nod!=0)
                {
                    rez[parent[nod]][nod]-=fluxm;
                    rez[nod][parent[nod]]+=fluxm;
                    nod=parent[nod];
                }
                flow+=fluxm;
            }
        }
    }
    return flow;
}
int main()
{
    r>>n;
    for(int i=1;i<=n;i++){
        int x, y;
        r>>x>>y;
        g[0].push_back(i);
        g[i].push_back(0);
        rez[0][i]=x;
        g[i+n].push_back(2*n+1);
        g[2*n+1].push_back(i+n);
        rez[i+n][2*n+1]=y;
    }
    for(int i=1;i<=n;i++){
        for(int j=n+1;j<=2*n;j++){
            if(i+n!=j){
                g[i].push_back(j);
                g[j].push_back(i);
                rez[i][j]=1;
            }
        }
    }
    w<<flux()<<"\n";
    for(int i=1;i<=n;i++){
        for(int j=n+1;j<=2*n;j++){
            if(i+n!=j && rez[i][j]==0){
                w<<i<<" "<<j-n<<"\n";
            }
        }
    }
    return 0;
}