Cod sursa(job #517051)

Utilizator gorgovanAurelian Namascu gorgovan Data 27 decembrie 2010 17:11:47
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#define pb push_back
vector<int> st[105],dr[105];
vector<int> G[10005];
int out[105],in[105];
bool map[105][105];
int viz[10005],l[10006],r[10006],adev[10006],adev1[10006],S,n,N,D,d;
ofstream fout("harta.out");


bool dfs(int x)
{
    if(viz[x]) return 0;
    viz[x]=1;
    vector<int>::iterator it;

    for(it=G[x].begin();it<G[x].end();it++)
    {
        if(!l[*it])//&&!map[adev1[x]][adev[*it]])
        {   map[adev1[x]][adev[*it]]=1;
            l[*it]=x;
            r[x]=*it;
            return 1;
        }
    }

    for(it=G[x].begin();it<G[x].end();it++)
    {
        if(dfs(l[*it]))//&&!map[adev1[x]][adev[*it]])
        {   map[adev1[x]][adev[*it]]=1;
            l[*it]=x;
            r[x]=*it;
            return 1;
        }
    }
    return 0;
}

void solve()
{
    int flow=0,ok=1, i;
     while(ok)
     {
         ok=0;
         for(i=1;i<=S;i++) viz[i]=0;

         for(i=1;i<=S;i++)
           if(!r[i])
            if(dfs(i))
            {
                flow++;
                ok=1;
            }
     }
     fout<<flow+1<<"\n";
     vector<int>::iterator it,jt;
     for(i=1;i<=n;i++)
     { //////////

         for(it=st[i].begin();it<st[i].end();it++)
         {

             if(r[*it])
             {
                fout<<i<<" "<<adev[r[*it]]<<"\n";
             }
         }
     }
}

void cit()
{int x,y,i,ii,iii;
    ifstream fin("harta.in");
    fin>>n;
    S=0;
    D=0;
    for(i=1;i<=n;i++)
    {
        fin>>x>>y;
        for(ii=D+1;ii<=D+y;ii++)
          adev[ii]=i;
        D+=y;

        out[i]=x;
        in[i]=y;
    }
    for(i=1;i<=D;i++)
      cout<<adev[i]<<" ";
    d=0;
    for(i=1;i<=n;i++)
    {
        d+=in[i];
        for(ii=1;ii<=out[i];ii++)
        {
        S++;
        st[i].pb(S);
        adev1[S]=i;
        for(iii=1;iii<=d-in[i];iii++)
        {
            G[S].pb(iii);
        }
        for(iii=d+1;iii<=D;iii++)
        {
            G[S].pb(iii);
        }
        }
    }
    vector<int>::iterator it,jt;
    for(i=1;i<=n;i++)
    {
         cout<<i<<": ";
         for(it=st[i].begin();it<st[i].end();it++)
         {
             for(jt=G[*it].begin();jt<G[*it].end();jt++)
             {
                 cout<<adev[*jt]<<" ";
             }
         }
         cout<<"\n";
    }
    fin.close();

}

int main()
{

    cit();

    solve();

    fout.close();
    return 0;


}