Cod sursa(job #886415)

Utilizator ericptsStavarache Petru Eric ericpts Data 22 februarie 2013 20:39:48
Problema Taramul Nicaieri Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 105
#define pb push_back
#define forEach(G) for( typeof(G.begin()) it = G.begin() ; it != G.end() ; ++ it)
int n;
int grad_in[maxn];
int grad_out[maxn];
bool u[maxn][maxn];
vector<int> start;
vector<int> end;
vector<int> graf[maxn];
struct comp
{
    public:
    inline bool operator() (const int &a,const int &b)const
    {
        return grad_in[a] > grad_in[b];
    }
};

int main()
{
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    scanf("%d",&n);
    int i,j,k;
    int show = 0;
    for(i=1;i<=n;++i)
    {
        scanf("%d %d",grad_in+i,grad_out+i);
        show += grad_in[i];

        if(grad_in[i])
            start.pb(i);
        if(grad_out[i])
            end.pb(i);
    }
    sort(start.begin(),start.end(),comp());
    k = end.size()-1;
    for(i=0;i<start.size();++i)
    {

        for(j=0;j<end.size();++j)
        {

            if(start[i] != end[j] && !u[start[i]][end[j]] && !u[end[j]][start[i]])
            {

                u[start[i]][end[j]] = u[end[j]][start[i]]=1;
                graf[start[i]].pb(end[j]);

                if(--grad_out[end[j]] == 0)
                {
                    end[j] = end[end.size()-1];
                    end.pop_back();
                    --j;
                }
                if(--grad_in[start[i]] == 0)
                    break;
            }
        }
    }
    printf("%d\n",show);
    for(i=1;i<=n;++i)
        forEach(graf[i])
            printf("%d %d\n",i,*it);
    return 0;
}