Cod sursa(job #2680641)

Utilizator robert.barbu27robert barbu robert.barbu27 Data 3 decembrie 2020 20:33:48
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda cuplajesiflux Marime 2.2 kb
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define inf 1000000000
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
const int NMAX=100;
int cap[2*NMAX+5][2*NMAX+5];
int n;
vector<int> adj[2*NMAX+5];
int source,dest,ant[2*NMAX+5];
bool bfs(int node)
{
    queue<int> q;
    vector<bool> viz(2*n+5,0);
    q.push(node);
    viz[node]=1;
    ant[node]=-1;
    while(!q.empty())
    {
        int crt=q.front();
       // cout<<crt<<" ";
        if(crt==dest) return 1;
        for(auto x:adj[crt])
        {
            if(viz[x]==0)
            {
                if(cap[crt][x]>0)
                {
                    viz[x]=1;
                    q.push(x);
                    ant[x]=crt;
                    //cout<<x<<" ";
                    if(x==dest)
                    {
                        return 1;
                    }
                }
            }
        }
        q.pop();
    }
    return 0;
}
int flow(int node,int flw)
{
    if(flw==0) return 0;
    while(node!=source)
    {
        flw=min(flw,cap[ant[node]][node]);
        node=ant[node];
        if(flw==0) return 0;
    }
    node=dest;
    while(node!=source)
    {
        cap[ant[node]][node]-=flw;
        cap[node][ant[node]]+=flw;
        node=ant[node];
    }
    return flw;

}
int main()
{

    f>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        f>>x>>y;
        adj[0].pb(i);
        adj[i].pb(0);
        adj[i+n].pb(2*n+1);
        adj[2*n+1].pb(i+n);
        cap[0][i]=x;
        cap[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){
            cap[i][j]=1;
            adj[i].pb(j);
            adj[j].pb(i);
            }

        }
    }
    source=0;
    dest=2*n+1;
    int sol=0;
    while(bfs(0))
    {
        sol+=flow(2*n+1,1e9);
        //cout<<0;

    }
    g<<sol<<'\n';
    for(int i=1;i<=n;i++)
    {
        for(int j=n+1;j<=2*n;j++)
        {
            if((i+n)!=j&&cap[i][j]==0)
            {
                g<<i<<" "<<j-n<<'\n';
            }
        }
    }







}