Cod sursa(job #2421051)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 14 mai 2019 00:25:23
Problema Taramul Nicaieri Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.78 kb
#include <iostream>
#include <cstdio>
#include <fstream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

vector<int> g[210];
vector<int> sol[110];
int n;
int c[210][210];
int in[110];
int out[110];
int dad[110];

int bfs(int s,int d)
{
    queue<int> q;
    bool viz[1010];
    memset(viz,0,sizeof viz);
    q.push(s);
    dad[s]=s;
    int crt;
    viz[0]=1;
    while(!q.empty())
    {
        crt=q.front(); q.pop();
      //  cout<<crt<<'\n';
        if(crt!=d)
        for(int u:g[crt])
        {
        //    cout<<u<<' '<<c[crt][u]<<'\n';
            if(!viz[u] && c[crt][u])
            {
                viz[u]=1;
                dad[u]=crt;
                q.push(u);
            }
        }
    }
    return viz[d];
}

int main()
{
    ifstream t1("harta.in");
    ofstream t2("harta.out");
    t1>>n;
    int i,j;
    for(i=1;i<=n;i++) t1>>out[i]>>in[i];
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
            {
                c[i][100+j]=1;
                g[i].push_back(100+j);
                g[100+j].push_back(i);
            }
    for(i=1;i<=n;i++)
    {
        g[0].push_back(i);
        g[i].push_back(0);
        c[0][i]=out[i];
        c[100+i][100+n+1]=in[i];
        g[100+i].push_back(100+n+1);
        g[100+n+1].push_back(100+i);
    }

   /* for(int u:g[0])
            cout<<u<<' '; cout<<'\n';

    for(i=1;i<=n;i++)
    {
        for(int u:g[i])
            cout<<u<<' '; cout<<'\n';
    }

    for(i=1;i<=n;i++)
    {
        for(int u:g[100+i])
            cout<<u<<' '; cout<<'\n';
    }*/


    int crt,maxim,flow=0,n1,n2;
    int nr=0;
    while(bfs(0,100+n+1))
    {
        //for(i=1;i<=n;i++) cout<<dad[i]<<' ';
        //for(i=1;i<=n;i++) cout<<dad[100+i]<<' '; cout<<'\n';

        for(int i=1;i<=n;i++)
        {
       //     cout<<i<<' ';
            dad[100+n+1]=100+i;
            crt=100+n+1;
            maxim=0x7fffffff;
            while(crt!=dad[crt])
            {
                if(maxim>c[dad[crt]][crt])
                {
                    n1=dad[crt]; n2=crt;
                    maxim=c[dad[crt]][crt];
                }
                crt=dad[crt];
            }

           // cout<<maxim<<'\n';
            if(maxim)
            {
                sol[ dad[100+i]].push_back(i);
            }
            flow+=maxim;
            crt=100+n+1;
            while(crt!=dad[crt])
            {
                c[crt][dad[crt]]+=maxim;
                c[dad[crt]][crt]-=maxim;
                crt=dad[crt];
            }
        }
     //   cout<<flow<<'\n';
    }
    t2<<flow<<'\n';
    for(i=1;i<=n;i++)
        for(int u:sol[i]) t2<<i<<' '<<u<<'\n';
    t1.close();
    t2.close();
    return 0;
}