Cod sursa(job #886480)

Utilizator ericptsStavarache Petru Eric ericpts Data 22 februarie 2013 21:27:45
Problema Taramul Nicaieri Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 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_out[a] > grad_out[b];
    }
};

struct in_comp
{
    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_out+i,grad_in+i);
        show += grad_out[i];

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

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