Cod sursa(job #1161745)

Utilizator NistorSergiuNistor Sergiu NistorSergiu Data 31 martie 2014 13:53:57
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define NMax 202
using namespace std;
int flux[NMax][NMax];
int cap[NMax][NMax];
vector <int> grr[NMax];
vector <pair<int,int> > sol;
queue <int> q;
int n,d,s;
int tata[NMax];
bool bfs()
{
    int i;
    int vf;
    for(i=1;i<=d;i++)
        tata[i]=0;
    tata[s]=s;
    q.push(s);
    while(!q.empty())
    {
        vf=q.front();
        q.pop();
        if(vf!=d)
        {
            for(i=0;i<grr[vf].size();i++)
                if((flux[vf][grr[vf][i]]!=cap[vf][grr[vf][i]])&&(!tata[grr[vf][i]]))
                {
                    tata[grr[vf][i]]=vf;
                    q.push(grr[vf][i]);
                }
        }
    }
    if(tata[d])
        return 1;
    return 0;
}
int main()
{
    int m;
    int i,j;
    int a,b;
    int fmin,vf;
    //int flow=0;
    ifstream f("harta.in");
    f>>n;
    d=2*n+2;
    s=2*n+1;
    for(i=1;i<=n;i++)
    {
        f>>a>>b;
        cap[s][i]=a;
        cap[i+n][d]=b;
        grr[s].push_back(i);
        grr[i].push_back(s);
        grr[i+n].push_back(d);
        grr[d].push_back(i+n);
    }
    f.close();
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
            {
                cap[i][j+n]=1;
                grr[i].push_back(j+n);
                grr[j+n].push_back(i);
            }
    while(bfs())
    {
        for(i=0;i<grr[d].size();i++)
            if((flux[grr[d][i]][d]!=cap[grr[d][i]][d])&&(tata[grr[d][i]]))
            {
                vf=grr[d][i];
                tata[d]=vf;
                fmin=cap[vf][d]-flux[vf][d];
                while(vf!=s)
                {
                    fmin=min(fmin,cap[tata[vf]][vf]-flux[tata[vf]][vf]);
                    vf=tata[vf];
                }
                if(fmin>0)
                {
                    vf=d;
                    while(vf!=s)
                    {
                        flux[tata[vf]][vf]+=fmin;
                        flux[vf][tata[vf]]-=fmin;
                        vf=tata[vf];
                    }
                    //flow+=fmin;
                }
            }
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(flux[i][j+n])
                sol.push_back(make_pair(i,j));
    ofstream g("harta.out");
    /*for(i=1;i<=2*n+2;i++)
    {
        for(j=1;j<=2*n+2;j++)
            g<<cap[i][j]<<" ";
        g<<'\n';
    }
    g<<'\n';
    for(i=1;i<=2*n+2;i++)
    {
        for(j=1;j<=2*n+2;j++)
            g<<flux[i][j]<<" ";
        g<<'\n';
    }
    */
    g<<sol.size()<<"\n";
    for(i=0;i<sol.size();i++)
        g<<sol[i].first<<" "<<sol[i].second<<'\n';
    //g<<flow;
    g.close();
    return 0;
}