Cod sursa(job #2130252)

Utilizator RaduXD1Nicolae Radu RaduXD1 Data 13 februarie 2018 16:10:19
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <fstream>
#include <vector>
#define DIM 203
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n,m,i,mini,ve,a,b,cap,j;
vector< pair<int, int> > sol;
int c[DIM][DIM], f[DIM][DIM];
int d[DIM], z[DIM], t[DIM];
vector<int> v[DIM];


int bfs()
{
    int p=1, u=1, i, nod,vecin;
    for(i=0;i<=m;i++)
        d[i]=0;
    z[1]=0;
    d[0]=1;
    while(p<=u)
    {
        nod=z[p];
        for(i=0;i<v[nod].size();i++)
        {
            vecin=v[nod][i];
            if(c[nod][vecin]>f[nod][vecin]&&d[vecin]==0)
            {
                u++;
                z[u]=vecin;
                d[vecin]=1;
                t[vecin]=nod;
            }
        }
        p++;
    }
    return d[m];
}

int main()
{
    fin>>n;
    m=2*n+1;
    for(i=1;i<=n;i++)
    {
        fin>>a>>b;
        v[0].push_back(i);
        c[0][i]=a;
        v[i+n].push_back(m);
        v[m].push_back(i+n);
        c[i+n][m]=b;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
            {
                v[i].push_back(j+n);
                v[j+n].push_back(i);
                c[i][j+n]=1;
            }
    while(bfs()==1)
    {
        for(i=0;i<v[m].size();i++)
        {
            ve=v[m][i];
            if(d[ve]==1&&c[ve][m]>f[ve][m])
            {
                a=ve;b=m;
                mini=c[ve][m]-f[ve][m];
                while(a!=0)
                {
                    mini=min(mini, c[a][b]-f[a][b]);
                    b=a;a=t[a];
                }
                mini=min(mini, c[a][b]-f[a][b]);
                a=ve;b=m;
                while(a!=0)
                {
                    f[a][b]+=mini;
                    f[b][a]-=mini;
                    b=a;a=t[a];
                }
                f[a][b]+=mini;
                f[b][a]-=mini;
                f[m][ve]+=mini;
            }
        }
    }
    for(i=1;i<=n;i++)
        for(j=n+1;j<=2*n;j++)
            if(f[i][j]==1)
                sol.push_back(make_pair(i, j-n));
    fout<<sol.size()<<"\n";
    for(i=0;i<sol.size();i++)
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";
    return 0;
}