Cod sursa(job #1069696)

Utilizator andreiiiiPopa Andrei andreiiii Data 30 decembrie 2013 13:55:07
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <algorithm>
#include <fstream>
#include <bitset>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
#define PII pair<int, int>
#define x first
#define y second

using namespace std;

const int N=300;

ifstream fin("harta.in");
ofstream fout("harta.out");

int C[N][N], F[N][N], degin[N], degout[N], Tr[N];
vector <int> g[N];
vector <PII> sol;
bitset <N> v;
int n;

int bfs()
{
    int x;
    queue <int> Q;
    v.reset();
    v[0]=1;
    for(Q.push(0);!Q.empty();Q.pop())
    {
        x=Q.front();
        if(x==2*n+1) continue;
        for(auto p: g[x])
        {
            if(C[x][p]==F[x][p]||v[p]) continue;
            v[p]=1;
            Q.push(p);
            Tr[p]=x;
        }
    }
    return v[2*n+1];
}

void get_flow()
{
    int i, fmin;
    while(bfs())
    {
        for(auto p: g[2*n+1])
        {
            if(F[p][2*n+1]==C[p][2*n+1]||!v[p]) continue;
            Tr[2*n+1]=p;
            fmin=INF;
            for(i=2*n+1;i;i=Tr[i])
            {
                fmin=min(fmin, C[Tr[i]][i]-F[Tr[i]][i]);
            }
            if(!fmin) continue;
            for(i=2*n+1;i;i=Tr[i])
            {
                F[Tr[i]][i]+=fmin;
                F[i][Tr[i]]-=fmin;
            }
        }
    }
}

int main()
{
    int i, j;
    fin>>n;
    for(i=1;i<=n;i++) fin>>degin[i]>>degout[i];
    for(i=1;i<=n;i++)
    {
        C[0][i]=degin[i];
        g[0].push_back(i);
        g[i].push_back(0);
        C[i+n][2*n+1]=degout[i];
        g[i+n].push_back(2*n+1);
        g[2*n+1].push_back(i+n);
        for(j=n+1;j<2*n+1;j++)
        {
            if(i!=j-n)
            {
                C[i][j]=1;
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
    get_flow();
    for(i=1;i<=n;i++)
    {
        for(j=n+1;j<2*n+1;j++)
        {
            if(F[i][j]==1) sol.push_back(make_pair(i, j-n));
        }
    }
    fout<<sol.size()<<"\n";
    for(auto it: sol) fout<<it.x<<" "<<it.y<<"\n";
    fin.close();
    fout.close();
}