Cod sursa(job #1774168)

Utilizator Bodo171Bogdan Pop Bodo171 Data 8 octombrie 2016 17:18:58
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
const int nmax=205;
vector<int> v[nmax];
int prec[nmax],q[nmax],fl[nmax][nmax],c[nmax][nmax];
int p,u,n,i,j,start,source,sink,sum,node;
bool ok;
bool bfs()
{
    for(i=1;i<=2*n+1;i++)
        prec[i]=0;
    prec[source]=-1;
    p=1;u=1;q[p]=source;
    while(p<=u)
    {
        start=q[p];p++;
        if(start==sink) return 1;
        for(j=0;j<v[start].size();j++)
        {
            i=v[start][j];
            if(prec[i]==0)
            {
                if(fl[start][i]<c[start][i])
                {
                prec[i]=start;
                u++;q[u]=i;
                }
                else
                {
                if(fl[i][start]>0)
                {
                    prec[i]=-start;
                    u++;q[u]=i;
                }
                }
            }
        }
    }
    return 0;
}
int main()
{
    ifstream f("harta.in");
    ofstream g("harta.out");
    f>>n;
    source=2*n+2;sink=2*n+1;
    for(i=1;i<=n;i++)
    {
        f>>c[source][i]>>c[n+i][sink];
        sum+=c[source][i];
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
         if(i!=j)
          {
          c[i][n+j]=1;
          v[i].push_back(n+j);
          v[n+j].push_back(i);
          }
    for(i=1;i<=n;i++)
    {
        v[source].push_back(i);
        v[i].push_back(source);
        v[n+i].push_back(sink);
    }
    ok=1;
    while(ok)
    {
        ok=bfs();
        if(ok==0) continue;
        node=sink;
        while(node!=source)
        {
            if(prec[node]>=0)
            {
                fl[prec[node]][node]++;
            }
            else
            {
                fl[node][-prec[node]]--;
            }
            node=prec[node];
            if(node<0) node*=-1;
        }
    }
    g<<sum<<'\n';
    for(i=1;i<=n;i++)
        for(j=n+1;j<=2*n;j++)
          if(fl[i][j]>0)
           g<<i<<' '<<j-n<<'\n';
    return 0;
}