Cod sursa(job #830600)

Utilizator robertpoeRobert Poenaru robertpoe Data 7 decembrie 2012 10:02:23
Problema Taramul Nicaieri Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
#define DIM 5000
#define FOR  for(it=v[nod].begin();it!=v[nod].end();++it)
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,nr=0;
int i,j,r;
int a,b;
int A[DIM][DIM];
int mat[DIM][DIM];
int v2[DIM];
int sol[2][DIM];
vector<int> v[DIM];
queue<int> q;
vector<int>::iterator it;
bitset<DIM> viz;
int s,d;
inline int bfs()
{
    viz.reset();
    q.push(s);
    int nod;
    while(!q.empty())
    {
        nod=q.front();
        q.pop();
        FOR
            if(!viz[*it]&&A[nod][*it]>mat[nod][*it])
            {
                v2[*it]=nod;
                viz[*it]=1;
                q.push(*it);
            }
    }
    return viz[d];
}
int main()
{
    f>>n;
    d=300;
    for(i=1;i<=n;++i)
    {
        f>>a>>b;
        v[0].push_back(i);
        A[0][i]=a;
        v[i+n].push_back(d);
        A[i+n][d]=b;
        v[d].push_back(i+n);
    }
    int j;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            if(i!=j&&A[0][i]&&A[j+n][d])
            {
                v[i].push_back(j+n);
                v[j+n].push_back(i);
                A[i][j+n] = 1;
            }
    do
    {
        for(it=v[d].begin();it!=v[d].end();++it)
        if(viz[*it]&&A[*it][d]>mat[*it][d])
        {
            v2[d]=*it;
            i=d;
            r=INF;
            while(i!=s)
            {
                r=min(r,A[v2[i]][i]-mat[v2[i]][i]);
                i=v2[i];
            }
            i=d;
            while(i!=s)
            {
                mat[v2[i]][i]+=r;
                mat[i][v2[i]]-=r;
                i=v2[i];
            }
        }
    }while(bfs());
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            if(mat[i][j+n]>0)
            {
                sol[0][++nr]=i;
                sol[1][nr]=j;
            }
    g<<nr<<"\n";
    for(i=1;i<=nr;++i)
        g<<sol[0][i]<<" "<<sol[1][i]<<"\n";
    return 0;
}